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
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, On the complexity of planning for agent teams and its implications for single agent planning, Adiabatic quantum programming: minor embedding with hard faults, Fixed-Parameter Tractability of Treewidth and Pathwidth, Graph Minors and Parameterized Algorithm Design
Uses Software
Cites Work
- 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
- 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
