deleted 2 characters in body
Source Link
Yaroslav Bulatov
  • 4.6k
  • 1
  • 22
  • 35

Given an edge-weighted directed graph, how do you sum over all weighted paths between A and B while using the smallest number of multiplications?

enter image description here

Isenter image description here Is there a name for this problem?

This comes up in automatic differentiation, and people have shown this to be NP-complete for general graphs. That paper however, relies on autodiff notation, is there an analogue from graph theory community?

Is anything known about tractability of this problem for special graph types? Using dynamic programming on path decomposition should scale exponentially in pathwidth.

I was wondering if this problem is still intractable when restricting to interval graphs

Given an edge-weighted directed graph, how do you sum over all weighted paths between A and B while using the smallest number of multiplications?

enter image description here

Is there a name for this problem?

This comes up in automatic differentiation, and people have shown this to be NP-complete for general graphs. That paper however, relies on autodiff notation, is an analogue from graph theory community?

Is anything known about tractability of this problem for special graph types? Using dynamic programming on path decomposition should scale exponentially in pathwidth.

I was wondering if this problem is still intractable when restricting to interval graphs

Given an edge-weighted directed graph, how do you sum over all weighted paths between A and B while using the smallest number of multiplications?

enter image description here Is there a name for this problem?

This comes up in automatic differentiation, and people have shown this to be NP-complete for general graphs. That paper however, relies on autodiff notation, is there an analogue from graph theory community?

Is anything known about tractability of this problem for special graph types? Using dynamic programming on path decomposition should scale exponentially in pathwidth.

I was wondering if this problem is still intractable when restricting to interval graphs

added 11 characters in body
Source Link
Yaroslav Bulatov
  • 4.6k
  • 1
  • 22
  • 35

Given an edge-weighted directed graph, how do you sum over all weighted paths between A and B withwhile using the smallest number of multiplications?

enter image description here

Is there a name for this problem?

This comes up in automatic differentiation, and people have shown this to be NP-complete for general graphs. That paper however, relies on autodiff notation, is an analogue from graph theory community?

Is anything known about tractability of this problem for special graph types? Using dynamic programming on path decomposition should scale exponentially in pathwidth.

I was wondering if this problem is still intractable when restricting to interval graphs

Given an edge-weighted directed graph, how do you sum over all weighted paths between A and B with the smallest number of multiplications?

enter image description here

Is there a name for this problem?

This comes up in automatic differentiation, and people have shown this to be NP-complete for general graphs. That paper however, relies on autodiff notation, is an analogue from graph theory community?

Is anything known about tractability of this problem for special graph types? Using dynamic programming on path decomposition should scale exponentially in pathwidth.

I was wondering if this problem is still intractable when restricting to interval graphs

Given an edge-weighted directed graph, how do you sum over all weighted paths between A and B while using the smallest number of multiplications?

enter image description here

Is there a name for this problem?

This comes up in automatic differentiation, and people have shown this to be NP-complete for general graphs. That paper however, relies on autodiff notation, is an analogue from graph theory community?

Is anything known about tractability of this problem for special graph types? Using dynamic programming on path decomposition should scale exponentially in pathwidth.

I was wondering if this problem is still intractable when restricting to interval graphs

edited title
Link
Yaroslav Bulatov
  • 4.6k
  • 1
  • 22
  • 35

Summing over all weighted paths optimally

added 144 characters in body
Source Link
Yaroslav Bulatov
  • 4.6k
  • 1
  • 22
  • 35
Loading
Source Link
Yaroslav Bulatov
  • 4.6k
  • 1
  • 22
  • 35
Loading