Finding outer-connected dominating sets in interval graphs

• 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.