A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs |
| |
Authors: | Elisabeth Gassner Johannes Hatzl |
| |
Affiliation: | 1. Department of Optimization and Discrete Mathematics, Graz University of Technology, Steyrergasse 30, 8010, Graz, Austria
|
| |
Abstract: | This paper concerns a domination problem in graphs with parity constraints. The task is to find a subset of the vertices with minimum cost such that for every vertex the number of chosen vertices in its neighbourhood has a prespecified parity. This problem is known to be ${mathcal NP}$ -hard for general graphs. A linear time algorithm was developed for series-parallel graphs and trees with unit cost and restricted to closed neighbourhoods. We present a linear time algorithm for the parity domination problem with open and closed neighbourhoods and arbitrary cost functions on graphs with bounded treewidth and distance-hereditary graphs. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |