| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427230 | Information Processing Letters | 2015 | 6 Pages |
•The outer-connected domination problem is abbreviated as the OCD problem.•The OCD problem was known to be linear-time solvable on proper interval graphs.•We solve the OCD problem on interval graphs in linear-time.•We do so by developing a chainless decomposition of graphs.
An outer-connected dominating set in a graph G=(V,E)G=(V,E) is a set S⊆VS⊆V such that each vertex not in S is adjacent to at least one vertex in S and the subgraph induced by V∖SV∖S is connected. In Keil and Pradhan (2013) [6], Keil and Pradhan gave a linear-time algorithm for finding a minimum outer-connected dominating set in a proper interval graph. In this paper, we generalize their result to find a minimum outer-connected dominating set in an interval graph in linear time.
