The eternal dominating set problem for proper interval graphs

DOI10.1016/j.ipl.2015.02.004zbMath1329.05224OpenAlexW2027125546MaRDI QIDQ2345856

Orlando Lee, Andrei Braga, Cid Carvalho De Souza

Publication date: 21 May 2015

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

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

zbMATH Keywords

combinatorial problemsproper interval graphseternal dominating set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Eternal domination: \(D\)-dimensional Cartesian and strong grids and everything in between, The eternal dominating set problem for interval graphs, Algorithmic complexity of outer independent Roman domination and outer independent total Roman domination, Total Roman domination for proper interval graphs, A method for eternally dominating strong grids, Eternal and Secure Domination in Graphs, New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs

Cites Work

• A linear-time algorithm for proper interval graph recognition
• Algorithmic graph theory and perfect graphs
• Protecting a graph with mobile guards
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item