Finding outer-connected dominating sets in interval graphs

DOI10.1016/j.ipl.2015.07.008zbMath1337.05100OpenAlexW1444318869MaRDI QIDQ495667

Chiou-Jiun Lin, Jia-Jie Liu, Yue-Li Wang

Publication date: 15 September 2015

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

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

zbMATH Keywords

graph algorithmsinterval graphsouter-connected dominationdominating setsproper interval graphs

Mathematics Subject Classification ID

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

Related Items (2)

A greedy algorithm for the fault-tolerant outer-connected dominating set problem ⋮ New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the outer-connected domination in graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Computing a minimum outer-connected dominating set for the class of chordal graphs
• An optimal parallel algorithm for computing cut vertices and blocks on interval graphs
• Algorithm and Hardness Results for Outer-connected Dominating Set in Graphs

This page was built for publication: Finding outer-connected dominating sets in interval graphs