Digraph width measures in parameterized algorithmics

DOI10.1016/j.dam.2013.10.038zbMath1285.05077OpenAlexW1963961865MaRDI QIDQ2442211

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

Publication date: 2 April 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2013.10.038

zbMATH Keywords

digraphclique-widthtree-widthparameterized complexityDAG-widthDAG-depth

Mathematics Subject Classification ID

Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Directed graphs (digraphs), tournaments (05C20)

Related Items (20)

An algorithmic metatheorem for directed treewidth ⋮ Augmenting weighted graphs to establish directed point-to-point connectivity ⋮ A survey on how the structure of precedence constraints may change the complexity class of scheduling problems ⋮ Computing directed Steiner path covers ⋮ Acyclic coloring parameterized by directed clique-width ⋮ Directed width parameters on semicomplete digraphs ⋮ Adapting the Directed Grid Theorem into an FPT Algorithm ⋮ Are there any good digraph width measures? ⋮ Twin-distance-hereditary digraphs ⋮ Safe sets and in-dominating sets in digraphs ⋮ Directed NLC-width ⋮ How to compute digraph width measures on directed co-graphs ⋮ On directed covering and domination problems ⋮ Homomorphisms to digraphs with large girth and oriented colorings of minimal series-parallel digraphs ⋮ Efficient computation of the oriented chromatic number of recursively defined digraphs ⋮ Efficient algorithms for measuring the funnel-likeness of DAGs ⋮ Comparing linear width parameters for directed graphs ⋮ Digraphs of Bounded Width ⋮ On Directed Covering and Domination Problems ⋮ Complexity dichotomy for oriented homomorphism of planar graphs with large girth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Courcelle's theorem -- a game-theoretic approach
• The dag-width of directed graphs
• On the algorithmic effectiveness of digraph decompositions and complexity measures
• Digraph decompositions and monotonicity in digraph searching
• Digraph measures: Kelly decompositions, games, and orderings
• On complexity of minimum leaf out-branching problem
• On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
• Disjoint directed and undirected paths and cycles in digraphs
• Minimum leaf out-branching and related problems
• The directed subgraph homeomorphism problem
• Graph minors. X: Obstructions to tree-decomposition
• The Steiner tree problem
• A partial k-arboretum of graphs with bounded treewidth
• Graph searching and a min-max theorem for tree-width
• Homomorphisms and oriented colorings of equivalence classes of oriented graphs
• Directed tree-width
• Automata, logics, and infinite games. A guide to current research
• A unified approach to polynomial algorithms on graphs of bounded (bi-)rank-width
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• The rank-width of edge-coloured graphs
• Parametrized complexity theory.
• 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
• Directed tree-width examples
• Intractability of Clique-Width Parameterizations
• Are There Any Good Digraph Width Measures?
• Parameterized Tractability of Edge-Disjoint Paths on Directed Acyclic Graphs
• Reflections on Multivariate Algorithmics and Problem Parameterization
• A New Algorithm for Finding Trees with Many Leaves
• Clique-Width and Parity Games
• Randomized Divide-and-Conquer: Improved Path, Matching, and Packing Algorithms
• Graph minors. II. Algorithmic aspects of tree-width
• On the Complexity of Timetable and Multicommodity Flow Problems
• Mathematical Foundations of Computer Science 2005
• The Decision Problem for a Class of First‐Order Formulas in Which all Disjunctions are Binary
• 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: Digraph width measures in parameterized algorithmics