Tweeted twitter.com/#!/StackCSTheory/status/117312665059196928
edited tags
Link
Suresh Venkat
  • 31.6k
  • 4
  • 90
  • 267
added 37 characters in body
Source Link
nomad
  • 211
  • 1
  • 5

I'm looking to link a problem I'm working on to a known NP-hard problem. I think I can model my problem as a resource constrained shortest path problem. However, the structure of my graph is not completely arbitrary. Thus, it will be useful to know when RCSP becomes hard. Is it hard for a DAG, for a treeplanar DAG, for a DAG with bounded degree? Any help would be greatly appreciated!

I'm looking to link a problem I'm working on to a known NP-hard problem. I think I can model my problem as a resource constrained shortest path problem. However, the structure of my graph is not completely arbitrary. Thus, it will be useful to know when RCSP becomes hard. Is it hard for a DAG, for a tree? Any help would be greatly appreciated!

I'm looking to link a problem I'm working on to a known NP-hard problem. I think I can model my problem as a resource constrained shortest path problem. However, the structure of my graph is not completely arbitrary. Thus, it will be useful to know when RCSP becomes hard. Is it hard for a DAG, for a planar DAG, for a DAG with bounded degree? Any help would be greatly appreciated!

Source Link
nomad
  • 211
  • 1
  • 5

On which classes of graphs is resource constrained shortest path (RCSP) NP-hard?

I'm looking to link a problem I'm working on to a known NP-hard problem. I think I can model my problem as a resource constrained shortest path problem. However, the structure of my graph is not completely arbitrary. Thus, it will be useful to know when RCSP becomes hard. Is it hard for a DAG, for a tree? Any help would be greatly appreciated!