Approximation algorithms for digraph width parameters
From MaRDI portal
Abstract: Several problems that are NP-hard on general graphs are efficiently solvable on graphs with bounded treewidth. Efforts have been made to generalize treewidth and the related notion of pathwidth to digraphs. Directed treewidth, DAG-width and Kelly-width are some such notions which generalize treewidth, whereas directed pathwidth generalizes pathwidth. Each of these digraph width measures have an associated decomposition structure. In this paper, we present approximation algorithms for all these digraph width parameters. In particular, we give an O(sqrt{logn})-approximation algorithm for directed treewidth, and an O({log}^{3/2}{n})-approximation algorithm for directed pathwidth, DAG-width and Kelly-width. Our algorithms construct the corresponding decompositions whose widths are within the above mentioned approximation factors.
Recommendations
- Digraph width measures in parameterized algorithmics
- On digraph width measures in parameterized algorithmics
- On the algorithmic effectiveness of digraph decompositions and complexity measures
- Approximation algorithms for treewidth
- On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures
Cites work
- A partial k-arboretum of graphs with bounded treewidth
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
- Approximation algorithms for treewidth
- Are there any good digraph width measures?
- Complexity of Finding Embeddings in a k-Tree
- DAG-Width and Parity Games
- DAG-width
- Digraph measures: Kelly decompositions, games, and orderings
- Directed path-width and monotonicity in digraph searching
- Directed tree-width
- Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
- Fugitive-search games on graphs and related parameters
- Graph searching and a min-max theorem for tree-width
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- Inapproximability of treewidth, one-shot pebbling, and related layout problems
- Intractability of clique-width parameterizations
- Introducing directed tree width
- Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- On digraph width measures in parameterized algorithmics
- On the algorithmic effectiveness of digraph decompositions and complexity measures
- On treewidth approximations.
- Searching and pebbling
- The dag-width of directed graphs
- Treewidth. Computations and approximations
- \(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems
Cited in
(9)- scientific article; zbMATH DE number 7650942 (Why is no real title available?)
- Digraphs of bounded width
- Directed pathwidth and palletizers
- On the algorithmic effectiveness of digraph decompositions and complexity measures
- On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures
- Width-restricted layering of acyclic digraphs with consideration of dummy nodes
- Parameterized Approximation Schemes Using Graph Widths
- A linear-time parameterized algorithm for computing the width of a DAG
- On tradeoffs between width- and fill-like graph parameters
This page was built for publication: Approximation algorithms for digraph width parameters
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q476883)
