Parameterized algorithm for eternal vertex cover

DOI10.1016/j.ipl.2010.05.029zbMath1234.68150WikidataQ60488635 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 tractability; graph algorithms; vertex cover; parameterized complexity; eternal vertex cover

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

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

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