Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs

DOI10.1016/j.dam.2004.01.013zbMath1084.05064OpenAlexW2123302126MaRDI QIDQ1764807

Jochen Alber, Rolf Niedermeier, Frederic Dorn

Publication date: 22 February 2005

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2004.01.013

zbMATH Keywords

planar graphsfixed-parameter tractabilityalgorithm engineeringexact algorihmstree decomposition of graphsVERTEX COVER

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

Graph Minors and Parameterized Algorithm Design ⋮ New analysis and computational study for the planar connected dominating set problem ⋮ Computing Bond Types in Molecule Graphs ⋮ A novel parameterised approximation algorithm for \textsc{minimum vertex cover} ⋮ Confronting intractability via parameters ⋮ An Experimental Study on Generating Planar Graphs ⋮ Tree decompositions of graphs: saving memory in dynamic programming ⋮ Tree decomposition and discrete optimization problems: a survey ⋮ Computational study on planar dominating set problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. X: Obstructions to tree-decomposition
• A partial k-arboretum of graphs with bounded treewidth
• Call routing and the ratcatcher
• On treewidth approximations.
• Memory requirements for table computations in partial \(k\)-tree algorithms
• Generating hard and diverse test sets for NP-hard graph problems
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Solving large FPT problems on coarse-grained parallel machines
• Vertex Cover: Further Observations and Further Improvements
• Planar Branch Decompositions I: The Ratcatcher
• Tree Decompositions with Small Cost
• Graph minors. II. Algorithmic aspects of tree-width
• Vertex packings: Structural properties and algorithms
• Approximation algorithms for NP-complete problems on planar graphs
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Linear-time computation of optimal subgraphs of decomposable graphs
• Parameterized complexity: exponential speed-up for planar graph problems
• Faster exact algorithms for hard problems: A parameterized point of view

This page was built for publication: Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs