Approximation algorithms for treewidth
From MaRDI portal
Publication:848843
DOI10.1007/S00453-008-9180-4zbMATH Open1187.68703OpenAlexW1973972417MaRDI QIDQ848843FDOQ848843
Recommendations
Cites Work
- scientific article; zbMATH DE number 4178809 (Why is no real title available?)
- scientific article; zbMATH DE number 3174052 (Why is no real title available?)
- scientific article; zbMATH DE number 3688740 (Why is no real title available?)
- scientific article; zbMATH DE number 48812 (Why is no real title available?)
- scientific article; zbMATH DE number 176254 (Why is no real title available?)
- scientific article; zbMATH DE number 176761 (Why is no real title available?)
- scientific article; zbMATH DE number 176762 (Why is no real title available?)
- scientific article; zbMATH DE number 1262790 (Why is no real title available?)
- scientific article; zbMATH DE number 475614 (Why is no real title available?)
- scientific article; zbMATH DE number 1759716 (Why is no real title available?)
- scientific article; zbMATH DE number 1361465 (Why is no real title available?)
- scientific article; zbMATH DE number 4121482 (Why is no real title available?)
- scientific article; zbMATH DE number 3349645 (Why is no real title available?)
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A sufficiently fast algorithm for finding close to optimal clique trees
- An Algorithm for Determining Whether the Connectivity of a Graph is at Leastk
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- Automata, Languages and Programming
- Call routing and the ratcatcher
- Complexity of Finding Embeddings in a k-Tree
- Constant factor approximation of vertex-cuts in planar graphs
- Easy problems for tree-decomposable graphs
- Fast approximation algorithms for multicommodity flow problems
- Graph minors. II. Algorithmic aspects of tree-width
- Graph minors. XIII: The disjoint paths problem
- Improved approximation algorithms for minimum-weight vertex separators
- Introduction to algorithms.
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Multiway cuts in node weighted graphs
- On implementing the push-relabel method for the maximum flow problem
- On simple characterizations of k-trees
- Representations of chordal graphs as subtrees of a tree
- Theorem proving with structured theories. (Preliminary report)
- Tree clustering for constraint networks
- Treewidth and minimum fill-in: Grouping the minimal separators
- Treewidth. Computations and approximations
Cited In (54)
- An improved parameterized algorithm for treewidth
- Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
- Towards fixed-parameter tractable algorithms for abstract argumentation
- Vertex coloring of graphs with few obstructions
- On Exact Algorithms for Treewidth
- On approximating tree spanners that are breadth first search trees
- 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
- Inapproximability of treewidth and related problems
- 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 no real title available?)
- Weighted Treewidth Algorithmic Techniques and Results
- Title not available (Why is no real title available?)
- Approximate tree decompositions of planar graphs in linear time
- 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 no real title available?)
- On exact algorithms for treewidth
- An improvement of Reed's treewidth approximation
- An improvement of Reed's treewidth approximation
- Automata, Languages and Programming
- Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth
- On treewidth approximations.
- A nearly-linear time algorithm for linear programs with small treewidth: a multiscale representation of robust central path
- On treewidth approximations
- Space saving by dynamic algebraization based on tree-depth
- Tree decompositions and social graphs
- Practical approximation algorithms for zero- and bounded-skew trees
- Title not available (Why is no real title available?)
- An Isomorphism-Invariant Distance Function on Propositional Formulas in CNF
- Title not available (Why is no real title available?)
- 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)
