On the vertex cover \(P_3\) problem parameterized by treewidth
From MaRDI portal
Publication:2410093
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
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
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