On the vertex cover \(P_3\) problem parameterized by treewidth

DOI10.1007/s10878-016-9999-6zbMath1381.90076OpenAlexW2472778302MaRDI QIDQ2410093

Lei Cui, Jing Yuan, Lidong Wu, Jian-hua Tu

Publication date: 17 October 2017

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-016-9999-6

zbMATH Keywords

treewidthtree decompositiongraph algorithmsparameterized complexityvertex cover \(P_3\) problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (6)

Unnamed Item ⋮ Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm ⋮ A multi-start iterated greedy algorithm for the minimum weight vertex cover \(P_3\) problem ⋮ Algorithm for online 3-path vertex cover ⋮ Hitting minors on bounded treewidth graphs. III. Lower bounds ⋮ Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms

Uses Software

• ComputeTW

Cites Work

• Unnamed Item
• Unnamed Item
• On the weighted \(k\)-path vertex cover problem
• A fixed-parameter algorithm for the vertex cover \(P_3\) problem
• On computing the minimum 3-path vertex cover and dissociation number of graphs
• A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
• A faster FPT algorithm for 3-path vertex cover
• Treewidth computations. I: Upper bounds
• The node-deletion problem for hereditary properties is NP-complete
• A partial k-arboretum of graphs with bounded treewidth
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
• A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
• Minimum \(k\)-path vertex cover
• On the vertex \(k\)-path cover
• Parametrized complexity theory.
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Kernels for Packing and Covering Problems
• A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion
• Fourier meets M\"{o}bius: fast subset convolution
• Graph minors. II. Algorithmic aspects of tree-width
• Parameterized complexity: exponential speed-up for planar graph problems
• Parameterized Algorithms
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems

This page was built for publication: On the vertex cover \(P_3\) problem parameterized by treewidth