Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs
From MaRDI portal
Publication:1764807
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
planar graphsfixed-parameter tractabilityalgorithm engineeringexact algorihmstree decomposition of graphsVERTEX COVER
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