A Note on the Parameterized Complexity of Unordered Maximum Tree Orientation. Böcker, S. & Damaschke, P. Discrete Appl Math, 160(10-11):1634–1638, 2012. doi abstract bibtex 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.
@Article{boecker12note,
author = {Sebastian B\"ocker and Peter Damaschke},
title = {A Note on the Parameterized Complexity of Unordered Maximum Tree Orientation},
journal = {Discrete Appl Math},
year = {2012},
volume = {160},
number = {10-11},
pages = {1634--1638},
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.},
doi = {10.1016/j.dam.2012.02.017},
file = {BoeckerDamaschke_NoteParameterizedComplexity_DAM_2012_preprint.pdf:2012/BoeckerDamaschke_NoteParameterizedComplexity_DAM_2012_preprint.pdf:PDF},
keywords = {jena; linkpdf; tree orientation; fpt; PABI},
owner = {Sebastian},
timestamp = {2011.11.18},
}
Downloads: 0
{"_id":"7HbSC3gRrsjzs7pvb","bibbaseid":"bcker-damaschke-anoteontheparameterizedcomplexityofunorderedmaximumtreeorientation-2012","authorIDs":[],"author_short":["Böcker, S.","Damaschke, P."],"bibdata":{"bibtype":"article","type":"article","author":[{"firstnames":["Sebastian"],"propositions":[],"lastnames":["Böcker"],"suffixes":[]},{"firstnames":["Peter"],"propositions":[],"lastnames":["Damaschke"],"suffixes":[]}],"title":"A Note on the Parameterized Complexity of Unordered Maximum Tree Orientation","journal":"Discrete Appl Math","year":"2012","volume":"160","number":"10-11","pages":"1634–1638","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.","doi":"10.1016/j.dam.2012.02.017","file":"BoeckerDamaschke_NoteParameterizedComplexity_DAM_2012_preprint.pdf:2012/BoeckerDamaschke_NoteParameterizedComplexity_DAM_2012_preprint.pdf:PDF","keywords":"jena; linkpdf; tree orientation; fpt; PABI","owner":"Sebastian","timestamp":"2011.11.18","bibtex":"@Article{boecker12note,\n author = {Sebastian B\\\"ocker and Peter Damaschke},\n title = {A Note on the Parameterized Complexity of Unordered Maximum Tree Orientation},\n journal = {Discrete Appl Math},\n year = {2012},\n volume = {160},\n number = {10-11},\n pages = {1634--1638},\n 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.},\n doi = {10.1016/j.dam.2012.02.017},\n file = {BoeckerDamaschke_NoteParameterizedComplexity_DAM_2012_preprint.pdf:2012/BoeckerDamaschke_NoteParameterizedComplexity_DAM_2012_preprint.pdf:PDF},\n keywords = {jena; linkpdf; tree orientation; fpt; PABI},\n owner = {Sebastian},\n timestamp = {2011.11.18},\n}\n\n","author_short":["Böcker, S.","Damaschke, P."],"key":"boecker12note","id":"boecker12note","bibbaseid":"bcker-damaschke-anoteontheparameterizedcomplexityofunorderedmaximumtreeorientation-2012","role":"author","urls":{},"keyword":["jena; linkpdf; tree orientation; fpt; PABI"],"metadata":{"authorlinks":{}}},"bibtype":"article","biburl":"https://git.bio.informatik.uni-jena.de/fleisch/literature/raw/master/group-literature.bib","creationDate":"2019-11-19T16:29:35.068Z","downloads":0,"keywords":["jena; linkpdf; tree orientation; fpt; pabi"],"search_terms":["note","parameterized","complexity","unordered","maximum","tree","orientation","böcker","damaschke"],"title":"A Note on the Parameterized Complexity of Unordered Maximum Tree Orientation","year":2012,"dataSources":["C5FtkvWWggFfMJTFX"]}