A linear time algorithm for liar's domination problem in proper interval graphs
From MaRDI portal
Publication:2445259
DOI10.1016/j.ipl.2013.07.012zbMath1284.05308OpenAlexW1993437988MaRDI QIDQ2445259
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
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