A linear time algorithm for liar's domination problem in proper interval graphs

DOI10.1016/j.ipl.2013.07.012zbMath1284.05308OpenAlexW1993437988MaRDI QIDQ2445259

B. S. Panda, Subhabrata Paul

Publication date: 14 April 2014

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

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

zbMATH Keywords

graph algorithmsproper interval graphsundirected path graphsliar's domination

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (13)

Liar's dominating sets in graphs ⋮ Linear kernels for \(k\)-tuple and liar's domination in bounded genus graphs ⋮ Fault tolerant detectors for distinguishing sets in graphs ⋮ Liar's dominating set problem on unit disk graphs ⋮ Liar’s Domination in 2D ⋮ Liar's domination in unit disk graphs ⋮ Hardness results, approximation and exact algorithms for liar's domination problem in graphs ⋮ Algorithmic complexity of outer independent Roman domination and outer independent total Roman domination ⋮ Various bounds for liar's domination number ⋮ Total Roman domination for proper interval graphs ⋮ On \(d\)-distance \(m\)-tuple \((\ell,r)\)-domination in graphs ⋮ Unnamed Item ⋮ New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear time recognition algorithm for proper interval graphs
• Liar's domination in graphs
• A recognition algorithm for the intersection graphs of paths in trees
• Incidence matrices and interval graphs
• Liar's domination
• On the Algorithmic Complexity of Total Domination
• Dominating Sets in Chordal Graphs
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
• Total domination in interval graphs

This page was built for publication: A linear time algorithm for liar's domination problem in proper interval graphs