Independent domination in chordal graphs |
| |
Authors: | Martin Farber |
| |
Institution: | Faculty of Mathematics, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1 |
| |
Abstract: | A graph chordal if it does not contain any cycle of length greater than three as an induced subgraph. A set of S of vertices of a graph G = (V,E) is independent if not two vertices in S are adjacent, and is dominating if every vertex in V?S is adjacent to some vertex in S. We present a linear algorithm to locate a minimum weight independent dominating set in a chordal graph with 0–1 vertex weights. |
| |
Keywords: | Linear algorithm independent dominating set chordal graph |
本文献已被 ScienceDirect 等数据库收录! |
|