Eternal connected vertex cover problem in graphs: complexity and algorithms

DOI10.1007/978-3-031-52213-0_13MaRDI QIDQ6547830

Kaustav K. Paul, Arti Pandey

Publication date: 31 May 2024

zbMATH Keywords

distance-hereditary graphsgraph algorithmschain graphscographsHamiltonian graphsMycielskianeternal connected vertex cover

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Unnamed Item
• Maximum independent sets in 3- and 4-regular Hamiltonian graphs
• Parameterized algorithm for eternal vertex cover
• Completely separable graphs
• Vertex and edge covers with clustering properties: Complexity and algorithms
• On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
• Hamiltonicity, diameter, domination, packing, and biclique partitions of Mycielski's graphs
• Eternal vertex cover on bipartite graphs
• Eternal connected vertex cover problem
• On graphs whose eternal vertex cover number and vertex cover number coincide
• A substructure based lower bound for eternal vertex cover number
• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
• The connected vertex cover problem in \(k\)-regular graphs
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• A new lower bound for the eternal vertex cover number of graphs
• Some algorithmic results for eternal vertex cover problem in graphs

This page was built for publication: Eternal connected vertex cover problem in graphs: complexity and algorithms