The k‐path vertex cover: General bounds and chordal graphs

DOI10.1002/net.22079zbMath1528.05054arXiv2105.02018OpenAlexW3206448149MaRDI QIDQ6087563

Zsolt Tuza, Csilla Bujtás, Marko Jakovac

Publication date: 12 December 2023

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2105.02018

zbMATH Keywords

transversalchordal graphplanar graphaverage degreewireless sensor network\(k\)-path vertex cover

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex degrees (05C07)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover
• On the weighted \(k\)-path vertex cover problem
• Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
• New results on \(k\)-independence of graphs
• On computing the minimum 3-path vertex cover and dissociation number of graphs
• A simpler PTAS for connected \(k\)-path vertex cover in homogeneous wireless sensor network
• Treewidth. Computations and approximations
• Generalized transversals, generalized vertex covers and node-fault-tolerance in graphs
• On the \(k\)-path vertex cover of some graph products
• A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
• New approach to the \(k\)-independence number of a graph
• Approximation algorithm for minimum connected 3-path vertex cover
• Approximation algorithms for minimum weight connected 3-path vertex cover
• On a relation between \(k\)-path partition and \(k\)-path vertex cover
• Minimum \(k\)-path vertex cover
• Parameterized algorithm for 3-path vertex cover
• The \(k\)-path vertex cover in Cartesian product graphs and complete bipartite graphs
• The \(k\)-path vertex cover of rooted product graphs
• The vertex cover \(P_3\) problem in cubic graphs
• On the vertex \(k\)-path cover
• An \(O^\ast ( 2 . 61 9^k )\) algorithm for \textsc{4-path vertex cover}
• On maximal paths and circuits of graphs
• Node-Deletion Problems on Bipartite Graphs
• Improved lower bounds on k‐independence