Minimum dominating cycles in outerplanar graphs |
| |
Authors: | Andrzej Proskurowski Maciej M Sysło |
| |
Affiliation: | (1) Department of Computer and Information Science, University of Oregon, Eugene, Oregon;(2) Computer Science Department, Washington State University, Pullman, Washington |
| |
Abstract: | Adominating cycle of a graph lies at a distance of at most one from all the vertices of the graph. The problem of finding the minimum size of such a cycle is proved to be difficult even when restricted to planar graphs. An efficient algorithm solving this problem is given for the class of two-connectedouterplanar graphs, in which all vertices lie on the exterior face in a plane embedding of the graph.On leave from Institute of Computer Science, University of Wrocaw, Wrocaw, Poland. |
| |
Keywords: | Domination NP-completeness Outerplanar graphs |
本文献已被 SpringerLink 等数据库收录! |
|