Name
Abstract | ||
|---|---|---|
In the Unordered Maximum Tree Orientation problem, a set P of paths in a tree and a parameter k is given, and we want to orient the edges in the tree such that all but at most k paths in P become directed paths. This is a more difficult variant of a well-studied problem in computational biology where the directions of paths in P are already given. We show that the parameterized complexity of the unordered version is between Edge Bipartization and Vertex Bipartization, and we give a characterization of orientable path sets in trees by forbidden substructures, which are cycles of a certain kind. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.dam.2012.02.017 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Graph orientation,Directed path,Parameterized reduction,Bipartization | Discrete mathematics,Combinatorics,Parameterized complexity,Vertex (geometry),Mathematics | Journal |
Volume | Issue | ISSN |
160 | 10 | 0166-218X |
Citations | PageRank | References |
0 | 0.34 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sebastian Böcker | 1 | 332 | 39.19 |
| Peter Damaschke | 2 | 471 | 56.99 |