An efficient polynomial time approximation scheme for the vertex cover \(P_3\) problem on planar graphs

DOI10.7151/dmgt.2060zbMath1401.05286OpenAlexW2794671365MaRDI QIDQ1630923

Yongtang Shi, Jian-hua Tu

Publication date: 5 December 2018

Published in: Discussiones Mathematicae. Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.7151/dmgt.2060

zbMATH Keywords

combinatorial optimizationplanar graphsbranch-widthEPTASvertex cover \(P_3\) problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Combinatorial optimization (90C27) Dynamic programming (90C39) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Computing connected-\(k\)-subgraph cover with connectivity requirement ⋮ Analyzing the 3-path vertex cover problem in planar bipartite graphs ⋮ Graph-based semi-supervised one class support vector machine for detecting abnormal lung sounds ⋮ 3-path vertex cover and dissociation number of hexagonal graphs

Cites Work

• Unnamed Item
• Unnamed Item
• A fixed-parameter algorithm for the vertex cover \(P_3\) problem
• Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
• On the complexity of embedding planar graphs to minimize certain distance measures
• 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
• Complexity and kernels for bipartition into degree-bounded induced graphs
• A faster FPT algorithm for 3-path vertex cover
• Graph minors. X: Obstructions to tree-decomposition
• Fixed-parameter algorithms for Vertex Cover \(P_3\)
• 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
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• The vertex cover \(P_3\) problem in cubic graphs
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion
• New upper bounds on the decomposability of planar graphs
• A Separator Theorem for Planar Graphs
• Node-Deletion Problems on Bipartite Graphs
• Approximation algorithms for NP-complete problems on planar graphs
• Optimal branch-decomposition of planar graphs in O ( n ³ ) Time
• A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems

This page was built for publication: An efficient polynomial time approximation scheme for the vertex cover \(P_3\) problem on planar graphs