On complexity of total vertex cover on subcubic graphs

DOI10.1007/978-3-319-55911-7_37MaRDI QIDQ2988847zbMATH OpenOpenAlexWikidataFDO

Authors Sheung-Hung Poon, Weilin Wang

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

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) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The vertex cover \(P_3\) problem in cubic graphs
• Vertex and edge covers with clustering properties: Complexity and algorithms
• The curse of connectivity: \(t\)-total vertex (edge) cover
• On total vertex covers and edge domination in graphs
• Complexity and algorithms for the connected vertex cover problem in 4-regular graphs

Cites work

• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Computing independent sets in graphs with large girth
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1270594 (Why is no real title available?)
• Optimal binary space partitions in the plane
• Some APX-completeness results for cubic graphs
• The Rectilinear Steiner Tree Problem is NP-Complete
• Vertex and edge covers with clustering properties: Complexity and algorithms

Cited in

(6)

• Vertex and edge covers with clustering properties: Complexity and algorithms
• On the complexity of the k-chain subgraph cover problem
• Total tessellation cover: bounds, hardness, and applications
• A substructure based lower bound for eternal vertex cover number
• The curse of connectivity: \(t\)-total vertex (edge) cover
• STRONG k-GEODETIC PROBLEM IN GRAPHS: COMPUTATIONAL COMPLEXITY AND SOME RESULTS

This page was built for publication: On complexity of total vertex cover on subcubic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2988847)