Enumerating minimal dominating sets in chordal bipartite graphs

被引：17

作者：

Golovach, Petr A. ^{[1
]}

Heggernes, Pinar ^{[1
]}

Kante, Mamadou M. ^{[2
]}

Kratsch, Dieter ^{[3
]}

Villanger, Yngve ^{[1
]}

机构：

[1] Univ Bergen, N-5020 Bergen, Norway

[2] Univ Blaise Pascal, Clermont Univ, LIMOS, CNRS, Aubiere, France

[3] Univ Lorraine, Metz, France

来源：

DISCRETE APPLIED MATHEMATICS | 2016年 / 199卷

基金：

欧洲研究理事会;

关键词：

Minimal dominating set; Enumeration; Output polynomial algorithm; MAXIMAL INDEPENDENT SETS; TRANSVERSAL HYPERGRAPHS; DUALIZATION; TIME; EDGE;

D O I：

10.1016/j.dam.2014.12.010

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We show that all minimal dominating sets of a chordal bipartite graph can be generated in incremental polynomial, hence output polynomial, time. Enumeration of minimal dominating sets in graphs is equivalent to enumeration of minimal transversals in hypergraphs. Whether the minimal transversals of a hypergraph can be enumerated in output polynomial time is a well-studied and challenging question that has been open for several decades. With this result we contribute to the known cases having an affirmative reply to this important question. (C) 2014 Elsevier B.V. All rights reserved.

引用

页码：30 / 36

页数：7

共 34 条

[1] Reverse search for enumeration [J].