Approximation algorithms for treewidth
From MaRDI portal
Publication:848843
DOI10.1007/S00453-008-9180-4zbMATH Open1187.68703OpenAlexW1973972417MaRDI QIDQ848843FDOQ848843
Authors: Eyal Amir 
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
Recommendations
Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Computer system organization (68M99)
Cites Work
- Introduction to algorithms.
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Call routing and the ratcatcher
- Graph minors. XIII: The disjoint paths problem
- Easy problems for tree-decomposable graphs
- Complexity of Finding Embeddings in a k-Tree
- Title not available (Why is that?)
- Multiway cuts in node weighted graphs
- Title not available (Why is that?)
- A sufficiently fast algorithm for finding close to optimal clique trees
- Graph minors. II. Algorithmic aspects of tree-width
- Representations of chordal graphs as subtrees of a tree
- Title not available (Why is that?)
- Treewidth. Computations and approximations
- On simple characterizations of k-trees
- Title not available (Why is that?)
- On implementing the push-relabel method for the maximum flow problem
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Treewidth and minimum fill-in: Grouping the minimal separators
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Tree clustering for constraint networks
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
- Title not available (Why is that?)
- Title not available (Why is that?)
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- Improved approximation algorithms for minimum-weight vertex separators
- An Algorithm for Determining Whether the Connectivity of a Graph is at Leastk
- Automata, Languages and Programming
- Fast approximation algorithms for multicommodity flow problems
- Theorem proving with structured theories. (Preliminary report)
- Constant factor approximation of vertex-cuts in planar graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (53)
- Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
- Towards fixed-parameter tractable algorithms for abstract argumentation
- Vertex coloring of graphs with few obstructions
- On sparsification for computing treewidth
- On Exact Algorithms for Treewidth
- On approximating tree spanners that are breadth first search trees
- An Improvement of Reed’s Treewidth Approximation
- Estimating the Size of Branch-and-Bound Trees
- Approximating the treewidth of AT-free graphs.
- A Branch and Bound Algorithm for Exact, Upper, and Lower Bounds on Treewidth
- Graph minors and parameterized algorithm design
- A \(c^k n\) 5-approximation algorithm for treewidth
- Approximate Turing Kernelization for Problems Parameterized by Treewidth
- Space-efficient vertex separators for treewidth
- Title not available (Why is that?)
- Weighted Treewidth Algorithmic Techniques and Results
- Title not available (Why is that?)
- Title not available (Why is that?)
- Approximate tree decompositions of planar graphs in linear time
- On the complexity of planning for agent teams and its implications for single agent planning
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
- Kernel bounds for disjoint cycles and disjoint paths
- Finding small-width connected path decompositions in polynomial time
- Boolean-width of graphs
- Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time
- Approximating sparsest cut in graphs of bounded treewidth
- Maximum matching width: new characterizations and a fast algorithm for dominating set
- Treewidth: Structure and Algorithms
- Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems
- Adiabatic quantum programming: minor embedding with hard faults
- Treewidth and the Computational Complexity of MAP Approximations
- An Experimental Study of the Treewidth of Real-World Graph Data
- Improved approximation algorithms for the average-case tree searching problem
- Approximation algorithms for digraph width parameters
- Fast Counting with Bounded Treewidth
- Title not available (Why is that?)
- On exact algorithms for treewidth
- An improvement of Reed's treewidth approximation
- Automata, Languages and Programming
- Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth
- On treewidth approximations.
- On treewidth approximations
- Space saving by dynamic algebraization based on tree-depth
- An improved parameterized algorithm for treewidth
- Tree decompositions and social graphs
- Practical approximation algorithms for zero- and bounded-skew trees
- Title not available (Why is that?)
- An Isomorphism-Invariant Distance Function on Propositional Formulas in CNF
- Title not available (Why is that?)
- Inapproximability of treewidth, one-shot pebbling, and related layout problems
- Typical sequences revisited -- computing width parameters of graphs
- Algorithms and complexity for Turaev-Viro invariants
- Fixed-parameter tractability of treewidth and pathwidth
Uses Software
This page was built for publication: Approximation algorithms for treewidth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q848843)
