New lower and upper bounds for graph treewidth

DOI10.1007/3-540-44867-5_6MaRDI QIDQ4426346zbMATH OpenFDO

Authors François Clautiaux, Jacques Carlier, A. Moukrim, Stéphane Nègre

Publication date 16 September 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2647/26470070.htm

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Heuristic and metaheuristic methods for computing graph treewidth
• Treewidth computations. I: Upper bounds
• Treewidth computations. II. Lower bounds
• Experimental and Efficient Algorithms
• An Iterative Heuristic Algorithm for Tree Decomposition

Cited in

(27)

• Treewidth of cocomparability graphs and a new order-theoretic parameter
• A branch-and-price-and-cut method for computing an optimal bramble
• Tree decomposition and discrete optimization problems: a survey
• Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
• Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
• Constructing Brambles
• Encoding Treewidth into SAT
• A New Lower Bound for Tree-Width Using Maximum Cardinality Search
• Canonizing Graphs of Bounded Tree Width in Logspace
• An Experimental Study of the Treewidth of Real-World Graph Data
• Computing treewidth on the GPU
• \textsc{ToTo}: an open database for computation, storage and retrieval of tree decompositions
• Treewidth of display graphs: bounds, brambles and applications
• Contraction and Treewidth Lower Bounds
• A managed Bayesian risk approach for decision making alternatives
• Algorithms – ESA 2004
• Algorithms – ESA 2005
• Heuristic and metaheuristic methods for computing graph treewidth
• Treewidth computations. II. Lower bounds
• Experimental and Efficient Algorithms
• Experimental and Efficient Algorithms
• Lower bounds for treewidth of product graphs
• Achievable sets, brambles, and sparse treewidth obstructions
• Treewidth lower bounds with brambles
• Treewidth computations. I: Upper bounds
• A cubic kernel for feedback vertex set and loop cutset
• On the maximum cardinality search lower bound for treewidth

This page was built for publication: New lower and upper bounds for graph treewidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4426346)