Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420157 | Discrete Applied Mathematics | 2012 | 5 Pages |
Abstract
In the Unordered Maximum Tree Orientation problem, a set PP of paths in a tree and a parameter kk is given, and we want to orient the edges in the tree such that all but at most kk paths in PP become directed paths. This is a more difficult variant of a well-studied problem in computational biology where the directions of paths in PP 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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Sebastian Böcker, Peter Damaschke,