On Complexity of Total Vertex Cover on Subcubic Graphs

DOI10.1007/978-3-319-55911-7_37zbMath1485.68198OpenAlexW2603705664WikidataQ62041698 ScholiaQ62041698MaRDI QIDQ2988847

Weilin Wang, Sheung-Hung Poon

Publication date: 19 May 2017

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-55911-7_37

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

STRONG k-GEODETIC PROBLEM IN GRAPHS: COMPUTATIONAL COMPLEXITY AND SOME RESULTS

Cites Work

• Unnamed Item
• Unnamed Item
• Vertex and edge covers with clustering properties: Complexity and algorithms
• Computing independent sets in graphs with large girth
• Some APX-completeness results for cubic graphs
• Optimal Binary Space Partitions in the Plane
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: On Complexity of Total Vertex Cover on Subcubic Graphs