Parameterized algorithm for eternal vertex cover

DOI10.1016/J.IPL.2010.05.029MaRDI QIDQ765521zbMATH OpenOpenAlexWikidataFDO

Authors Serge Gaspers, Petr A. Golovach, Dieter Kratsch, Saket Saurabh, 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

graph algorithmsparameterized complexityvertex coverfixed parameter tractabilityeternal vertex cover

Mathematics Subject Classification ID

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

Recommendations

• Some algorithmic results for eternal vertex cover problem in graphs
• An eternal vertex cover problem
• Eternal connected vertex cover problem
• Parameterized complexity of Vertex Cover variants
• Deterministic parameterized connected vertex cover
• Eternal vertex cover on bipartite graphs
• An improved fixed-parameter algorithm for vertex cover
• Algorithms and Data Structures

Cites work

• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• Capacitated Domination and Covering: A Parameterized Perspective
• Edge protection in graphs
• Enumerate and expand: Improved algorithms for connected vertex cover and tree cover
• Improved Parameterized Upper Bounds for Vertex Cover
• Improved Upper Bounds for Partial Vertex Cover
• On problems without polynomial kernels
• Parameterized complexity of Vertex Cover variants
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles

Cited in

(16)

• On graphs whose eternal vertex cover number and vertex cover number coincide
• A substructure based lower bound for eternal vertex cover number
• On graphs with minimal eternal vertex cover number
• Disentangling the computational complexity of network untangling
• Representation of the eternal vertex cover problem as a dynamic Stackelberg game
• Graphs with equal eternal vertex cover and eternal domination numbers
• What Is Known About Vertex Cover Kernelization?
• Some algorithmic results for eternal vertex cover problem in graphs
• Some algorithmic results for eternal vertex cover problem in graphs
• A new lower bound for the eternal vertex cover number of graphs
• Stability of vertex covers in a game with finitely many steps
• \(m\)-secure vertex cover of a graph
• An eternal vertex cover problem
• Eternal vertex cover on bipartite graphs
• To satisfy impatient web surfers is hard
• Eternal connected vertex cover problem in graphs: complexity and algorithms

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

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