✦ LIBER ✦

Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs

✍ Scribed by Dieter Kratsch

Publisher: Elsevier Science
Year: 1990
Tongue: English
Weight: 914 KB
Volume: 86
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(90)90363-m

No coin nor oath required. For personal study only.

✦ Synopsis

We study a new version of the domination problem in which the dominating set is required to be a clique. The minimum dominating clique problem is NP-complete for split graphs and, hence, for chordal graphs. We show that for two other important subclasses of chordal graphs the problem is solvable efficiently. We present an O(m . logn) algorithm for strongly chordal graphs and an O(n") algorithm for undirected path graphs.

📜 SIMILAR VOLUMES

The degree-preserving spanning tree prob

The degree-preserving spanning tree problem in strongly chordal and directed path graphs

✍ Ching-Chi Lin; Gerard J. Chang; Gen-Huey Chen 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 108 KB

## Abstract Suppose __G__ is a connected graph and __T__ a spanning tree of __G__. A vertex __v__ ε __V__(__G__) is said to be a degree‐preserving vertex if its degree in __T__ is the same as its degree in __G__. The degree‐preserving spanning tree problem is to find a spanning tree __T__ of a conn