A linear algorithm for the domination number of a series-parallel graph |
| |
Authors: | Tohru Kikuno Noriyoshi Yoshida Yoshiaki Kakuda |
| |
Affiliation: | Faculty of Engineering, Hiroshima University, Higashi-Hiroshima, Japan |
| |
Abstract: | A vertex u in an undirected graph G = (V, E) is said to dominate all its adjacent vertices and itself. A subset D of V is a dominating set in G if every vertex in G is dominated by a vertex in D, and is a minimum dominating set in G if no other dominating set in G has fewer vertices than D. The domination number of G is the cardinality of a minimum dominating set in G.The problem of determining, for a given positive integer k and an undirected graph G, whether G has a dominating set D in G satisfying ¦D¦ ≤ k, is a well-known NP-complete problem. Cockayne have presented a linear time algorithm for finding a minimum dominating set in a tree. In this paper, we will present a linear time algorithm for finding a minimum dominating set in a series-parallel graph. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|