On Digraph Width Measures in Parameterized Algorithmics

DOI10.1007/978-3-642-11269-0_15zbMath1273.68276OpenAlexW2118722432MaRDI QIDQ3656861

Alexander Langer, Petr Hliněný, Jan Obdržálek, Robert Ganian, Joachim Kneis, Peter Rossmanith

Publication date: 14 January 2010

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

Full work available at URL: https://doi.org/10.1007/978-3-642-11269-0_15

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (17)

Computing the zig-zag number of directed graphs ⋮ The rank-width of edge-coloured graphs ⋮ Hypertree-depth and minors in hypergraphs ⋮ Directed elimination games ⋮ Digraph decompositions and monotonicity in digraph searching ⋮ On the algorithmic effectiveness of digraph decompositions and complexity measures ⋮ How to compute digraph width measures on directed co-graphs ⋮ Approximation algorithms for digraph width parameters ⋮ The treewidth of proofs ⋮ LIFO-search: a min-max theorem and a searching game for cycle-rank and tree-depth ⋮ Unnamed Item ⋮ Are There Any Good Digraph Width Measures? ⋮ LIFO-Search on Digraphs: A Searching Game for Cycle-Rank ⋮ A Slice Theoretic Approach for Embedding Problems on Digraphs ⋮ A Polynomial Time Algorithm for Bounded Directed Pathwidth ⋮ Digraphs of Bounded Width ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Digraph measures: Kelly decompositions, games, and orderings
• On complexity of minimum leaf out-branching problem
• Disjoint directed and undirected paths and cycles in digraphs
• The directed subgraph homeomorphism problem
• Graph minors. X: Obstructions to tree-decomposition
• The Steiner tree problem
• Homomorphisms and oriented colorings of equivalence classes of oriented graphs
• Directed tree-width
• Automata, logics, and infinite games. A guide to current research
• Linear time solvable optimization problems on graphs of bounded clique-width
• Tree-depth, subgraph coloring and homomorphism bounds
• Directed path-width and monotonicity in digraph searching
• Vertex disjoint paths on clique-width bounded graphs
• Transition graphs and the star-height of regular events
• Graph Operations Characterizing Rank-Width and Balanced Graph Expressions
• DAG-width
• On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures
• Clique-Width and Parity Games
• Better Polynomial Algorithms on Graphs of Bounded Rank-Width
• Randomized Divide-and-Conquer: Improved Path, Matching, and Packing Algorithms
• Graph minors. II. Algorithmic aspects of tree-width
• Digraph Decompositions and Monotonicity in Digraph Searching
• DAG-Width and Parity Games
• Mathematical Foundations of Computer Science 2005
• Logic for Programming, Artificial Intelligence, and Reasoning
• SOFSEM 2006: Theory and Practice of Computer Science
• Computer Aided Verification
• Finding Branch-Decompositions and Rank-Decompositions

This page was built for publication: On Digraph Width Measures in Parameterized Algorithmics