Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
Mark JonesDaniel LokshtanovM. S. RamanujanSaket SaurabhOndrej SuchýPublished in: CoRR (2012)
Keyphrases
- parameterized complexity
- steiner tree
- minimum spanning tree
- bounded treewidth
- spanning tree
- fixed parameter tractable
- facility location
- shortest path
- graph theoretic
- global constraints
- weighted graph
- directed graph
- symmetry breaking
- graph theory
- special case
- bipartite graph
- traveling salesman problem
- integrity constraints
- binary images