Other formats:
BibTeX
LaTeX
RIS
@inproceedings{863704,
author = {Ganian, Robert and Hliněný, Petr and Obdržálek, Jan and Langer, Alexander and Kneis, Joachim and Rossmanith, Peter},
address = {Berlin},
booktitle = {IWPEC 2009: International Workshop on Parameterized and Exact Computation, Lecture Notes in Computer Science},
doi = {http://dx.doi.org/10.1007/978-3-642-11269-0_15},
edition = {5917},
keywords = {digraph; DAG-width; bi-rank-width; parameterized complexity},
howpublished = {tištěná verze "print"},
language = {eng},
location = {Berlin},
isbn = {978-3-642-11268-3},
pages = {185-197},
publisher = {Springer Verlag},
title = {On Digraph Width Measures in Parameterized Algorithmics},
url = {http://dx.doi.org/10.1007/978-3-642-11269-0_15},
year = {2009}
}
TY - JOUR
ID - 863704
AU - Ganian, Robert - Hliněný, Petr - Obdržálek, Jan - Langer, Alexander - Kneis, Joachim - Rossmanith, Peter
PY - 2009
TI - On Digraph Width Measures in Parameterized Algorithmics
PB - Springer Verlag
CY - Berlin
SN - 9783642112683
KW - digraph
KW - DAG-width
KW - bi-rank-width
KW - parameterized complexity
UR - http://dx.doi.org/10.1007/978-3-642-11269-0_15
N2 - In contrast to undirected width measures (such as treewidth or clique-width), which have provided many important algorithmic applications, analogous measures for digraphs such as DAGwidth or Kelly-width do not seem so successful. Several recent papers, e.g. those of Kreutzer-Ordyniak, Dankelmann-Gutin-Kim, or Lampis-Kaouri-Mitsou, have given some evidence for this. We support this direction by showing that many quite different problems remain hard even on graph classes that are restricted very beyond simply having small DAG-width. To this end, we introduce new measures K-width and DAGdepth. On the positive side, we also note that taking Kanté's directed generalization of rank-width as a parameter makes many problems fixed parameter tractable.
ER -
GANIAN, Robert, Petr HLINĚNÝ, Jan OBDRŽÁLEK, Alexander LANGER, Joachim KNEIS and Peter ROSSMANITH. On Digraph Width Measures in Parameterized Algorithmics. In \textit{IWPEC 2009: International Workshop on Parameterized and Exact Computation, Lecture Notes in Computer Science}. 5917th ed. Berlin: Springer Verlag, 2009, p.~185-197. ISBN~978-3-642-11268-3. Available from: https://dx.doi.org/10.1007/978-3-642-11269-0\_{}15.
|
