Approximation algorithms for treewidth
From MaRDI portal
Publication:848843
DOI10.1007/s00453-008-9180-4zbMath1187.68703MaRDI 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
68R10: Graph theory (including graph drawing) in computer science
68M99: Computer system organization
68W25: Approximation algorithms
Related Items
Unnamed Item, Unnamed Item, Tree decompositions and social graphs, Approximate tree decompositions of planar graphs in linear time, Vertex coloring of graphs with few obstructions, Beyond bidimensionality: parameterized subexponential algorithms on directed graphs, Approximation algorithms for digraph width parameters, Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time, Kernel bounds for disjoint cycles and disjoint paths, Boolean-width of graphs, Towards fixed-parameter tractable algorithms for abstract argumentation, An improvement of Reed's treewidth approximation, Algorithms and complexity for Turaev-Viro invariants, Finding small-width connected path decompositions in polynomial time, Space saving by dynamic algebraization based on tree-depth, Maximum matching width: new characterizations and a fast algorithm for dominating set, On the complexity of planning for agent teams and its implications for single agent planning, Adiabatic quantum programming: minor embedding with hard faults, A $c^k n$ 5-Approximation Algorithm for Treewidth, Fixed-Parameter Tractability of Treewidth and Pathwidth, Graph Minors and Parameterized Algorithm Design
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