Approximation algorithms for treewidth
From MaRDI portal
Publication:848843
DOI10.1007/s00453-008-9180-4zbMath1187.68703OpenAlexW1973972417MaRDI QIDQ848843
Publication date: 23 February 2010
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-008-9180-4
Graph theory (including graph drawing) in computer science (68R10) Computer system organization (68M99) Approximation algorithms (68W25)
Related Items (25)
An Improvement of Reed’s Treewidth Approximation ⋮ Approximate tree decompositions of planar graphs in linear time ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ Graph Minors and Parameterized Algorithm Design ⋮ Vertex coloring of graphs with few obstructions ⋮ Space-efficient vertex separators for treewidth ⋮ Space saving by dynamic algebraization based on tree-depth ⋮ Maximum matching width: new characterizations and a fast algorithm for dominating set ⋮ Beyond bidimensionality: parameterized subexponential algorithms on directed graphs ⋮ An Isomorphism-Invariant Distance Function on Propositional Formulas in CNF ⋮ Kernel bounds for disjoint cycles and disjoint paths ⋮ Typical sequences revisited -- computing width parameters of graphs ⋮ On the complexity of planning for agent teams and its implications for single agent planning ⋮ Approximation algorithms for digraph width parameters ⋮ Adiabatic quantum programming: minor embedding with hard faults ⋮ An improvement of Reed's treewidth approximation ⋮ Towards fixed-parameter tractable algorithms for abstract argumentation ⋮ Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time ⋮ Boolean-width of graphs ⋮ A $c^k n$ 5-Approximation Algorithm for Treewidth ⋮ An Experimental Study of the Treewidth of Real-World Graph Data ⋮ Algorithms and complexity for Turaev-Viro invariants ⋮ Finding small-width connected path decompositions in polynomial time ⋮ Tree decompositions and social graphs ⋮ Unnamed Item
Uses Software
Cites Work
- Tree clustering for constraint networks
- Call routing and the ratcatcher
- Treewidth. Computations and approximations
- On implementing the push-relabel method for the maximum flow problem
- On simple characterizations of k-trees
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- Fast approximation algorithms for multicommodity flow problems
- Graph minors. XIII: The disjoint paths problem
- Treewidth and Minimum Fill-in: Grouping the Minimal Separators
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Easy problems for tree-decomposable graphs
- Constant factor approximation of vertex-cuts in planar graphs
- Improved approximation algorithms for minimum-weight vertex separators
- Graph minors. II. Algorithmic aspects of tree-width
- Complexity of Finding Embeddings in a k-Tree
- Representations of chordal graphs as subtrees of a tree
- An Algorithm for Determining Whether the Connectivity of a Graph is at Leastk
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
- Multiway cuts in node weighted graphs
- Automata, Languages and Programming
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A sufficiently fast algorithm for finding close to optimal clique trees
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Approximation algorithms for treewidth
