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.
|