Are There Any Good Digraph Width Measures?

DOI10.1007/978-3-642-17493-3_14zbMath1309.68150arXiv1004.1485OpenAlexW3099288604MaRDI QIDQ3058698

Daniel Meister, Somnath Sikdar, Robert Ganian, Jan Obdržálek, Joachim Kneis, Petr Hliněný, Peter Rossmanith

Publication date: 7 December 2010

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1004.1485

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (15)

An algorithmic metatheorem for directed treewidth ⋮ On the monotonicity of process number ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ The rank-width of edge-coloured graphs ⋮ Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking ⋮ Directed elimination games ⋮ Directed NLC-width ⋮ Digraph decompositions and monotonicity in digraph searching ⋮ Digraphs of bounded elimination width ⋮ Digraph width measures in parameterized algorithmics ⋮ Approximation algorithms for digraph width parameters ⋮ An extended tree-width notion for directed graphs related to the computation of permanents ⋮ DAG-Width and Circumference of Digraphs ⋮ On width measures and topological problems on semi-complete digraphs ⋮ Unnamed Item

Cites Work

• Digraph measures: Kelly decompositions, games, and orderings
• Graph minors. X: Obstructions to tree-decomposition
• Quickly excluding a planar graph
• Directed tree-width
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Easy problems for tree-decomposable graphs
• Treewidth: Characterizations, Applications, and Computations
• DAG-width
• On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures
• On Digraph Width Measures in Parameterized Algorithmics
• Graph minors. II. Algorithmic aspects of tree-width
• DAG-Width and Parity Games
• Mathematical Foundations of Computer Science 2005

This page was built for publication: Are There Any Good Digraph Width Measures?