Approximation algorithms for digraph width parameters

DOI10.1016/j.tcs.2014.10.009zbMath1303.68157arXiv1107.4824OpenAlexW2018558025MaRDI QIDQ476883

Akash Kumar, Nishad Kothari, Shiva Kintali

Publication date: 2 December 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmsdirected pathwidthdirected treewidthDAG-widtharboreal decompositionDAG-decompositiondirected path decompositiondirected vertex separatorsKelly decompositionKelly-width

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20)

Related Items

Directed Pathwidth and Palletizers ⋮ Digraphs of Bounded Width

Cites Work

• Unnamed Item
• Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking
• The dag-width of directed graphs
• On the algorithmic effectiveness of digraph decompositions and complexity measures
• Approximation algorithms for treewidth
• Digraph measures: Kelly decompositions, games, and orderings
• A partial k-arboretum of graphs with bounded treewidth
• Graph searching and a min-max theorem for tree-width
• Treewidth. Computations and approximations
• Fugitive-search games on graphs and related parameters
• On treewidth approximations.
• Searching and pebbling
• Directed tree-width
• Directed path-width and monotonicity in digraph searching
• Intractability of Clique-Width Parameterizations
• Are There Any Good Digraph Width Measures?
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems
• O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
• DAG-width
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• On Digraph Width Measures in Parameterized Algorithmics
• Complexity of Finding Embeddings in a k-Tree
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
• DAG-Width and Parity Games