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

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