CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

A note on the parameterized complexity of unordered maximum tree orientation

Sebastian Böcker ; Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers) ; Institutionen för data- och informationsteknik, Datavetenskap, Bioinformatik (Chalmers))
Discrete Applied Mathematics (0166-218X). Vol. 160 (2012), 10-11, p. 1634-1638.
[Artikel, refereegranskad vetenskaplig]

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.

Nyckelord: graph orientation, directed path, parameterized reduction, bipartization

Den här publikationen ingår i följande styrkeområden:

Läs mer om Chalmers styrkeområden  

Denna post skapades 2012-05-11. Senast ändrad 2015-02-11.
CPL Pubid: 157545


Läs direkt!

Länk till annan sajt (kan kräva inloggning)


Denna publikation är ett resultat av följande projekt:

Generalized and fast search strategies for parameterized problems (VR//2010-4661)