Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
On Digraph Width Measures in Parameterized Algorithmics
verfasst von : Robert Ganian, Petr Hliněný, Joachim Kneis, Alexander Langer, Jan Obdržálek, Peter Rossmanith
Erschienen in: Parameterized and Exact Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In contrast to undirected width measures (such as tree-width or clique-width), which have provided many important algorithmic applications, analogous measures for digraphs such as DAG-width 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 DAG-depth. 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.