Minimum Dominating Cycles in Outerplanar Graphs
Andrzej Proskurowski, Maciej Sysko
Committee:
Technical Report(May 1980)
Keywords:

A dominating cycle of a graph lies at distance at most one from all the vertices of the graph. The problem of finding minmum size such cycle is proved hard even when restricted to planar graphs. An efficient algorithm solving this problem is given for the class of outerplanar graphs, in which all vertices lie on the exterior face in a plane embedding of the graph.