Parameterized algorithm for eternal vertex cover

DOI10.1016/J.IPL.2010.05.029zbMath1234.68150OpenAlexW2125648129WikidataQ60488635 ScholiaQ60488635MaRDI QIDQ765521

Dieter Kratsch, Serge Gaspers, Saket Saurabh, Petr A. Golovach, Fedor V. Fomin

Publication date: 19 March 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2010.05.029

zbMATH Keywords

fixed parameter tractabilitygraph algorithmsvertex coverparameterized complexityeternal vertex cover

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (11)

On graphs whose eternal vertex cover number and vertex cover number coincide ⋮ Some algorithmic results for eternal vertex cover problem in graphs ⋮ Disentangling the computational complexity of network untangling ⋮ What Is Known About Vertex Cover Kernelization? ⋮ To satisfy impatient web surfers is hard ⋮ A substructure based lower bound for eternal vertex cover number ⋮ m-Secure vertex cover of a graph ⋮ Graphs with equal eternal vertex cover and eternal domination numbers ⋮ A new lower bound for the eternal vertex cover number of graphs ⋮ Eternally dominating large grids ⋮ Eternal vertex cover on bipartite graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Enumerate and expand: Improved algorithms for connected vertex cover and tree cover
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
• On problems without polynomial kernels
• Parameterized complexity of Vertex Cover variants
• Capacitated Domination and Covering: A Parameterized Perspective
• Improved Upper Bounds for Partial Vertex Cover
• Improved Parameterized Upper Bounds for Vertex Cover

This page was built for publication: Parameterized algorithm for eternal vertex cover