Reduction algorithms for graphs of small treewidth

DOI10.1006/inco.2000.2958zbMath1008.05140OpenAlexW1973347908WikidataQ59567926 ScholiaQ59567926MaRDI QIDQ1854433

Babette van Antwerpen-de Fluiter, Hans L. Bodlaender

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://dspace.library.uu.nl/handle/1874/17374

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (25)

A Retrospective on (Meta) Kernelization ⋮ On the parameterized complexity of maximum degree contraction problem ⋮ Kernelization – Preprocessing with a Guarantee ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ Lower bounds for protrusion replacement by counting equivalence classes ⋮ Sparse obstructions for minor-covering parameters ⋮ On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem ⋮ Finite Integer Index of Pathwidth and Treewidth ⋮ Problems hard for treewidth but easy for stable gonality ⋮ A faster parameterized algorithm for pseudoforest deletion ⋮ Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds ⋮ Confronting intractability via parameters ⋮ A generalization of Nemhauser and Trotter's local optimization theorem ⋮ On structural parameterizations of the bounded-degree vertex deletion problem ⋮ Explicit linear kernels for packing problems ⋮ On the Parameterized Complexity of Maximum Degree Contraction Problem. ⋮ Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width ⋮ Unnamed Item ⋮ Hitting Forbidden Minors: Approximation and Kernelization ⋮ Measuring what matters: a hybrid approach to dynamic programming with treewidth ⋮ Bidimensionality and Kernels ⋮ Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth. ⋮ On bounded-degree vertex deletion parameterized by treewidth ⋮ Kernelization: New Upper and Lower Bound Techniques ⋮ Noetherianity up to conjugation of locally diagonal inverse limits

Cites Work

• Characterization of partial 3-trees in terms of three structures
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Topology of series-parallel networks
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Algorithms finding tree-decompositions of graphs
• Easy problems for tree-decomposable graphs
• Characterization and Recognition of Partial 3-Trees
• The Recognition of Series Parallel Digraphs
• Parallel Algorithms with Optimal Speedup for Bounded Treewidth
• An algebraic theory of graph reduction
• Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Reduction algorithms for graphs of small treewidth