Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs
type: Item
instance of: scholarly article
title: Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs
zbMATH Open document ID: 0729.05046
DOI: 10.1016/0012-365X(90)90363-M
author: Dieter Kratsch
published in: Discrete Mathematics
publication date: 1990-01-01T00:00:00Z
review text: A set of vertices in a graph is called a dominating set if every vertex not in the set is adjacent to at least one vertex in the set. A dominating clique is a dominating set that induces a complete subgraph. The problem of locating a dominating clique of minimum cardinality is known to be NP-complete for general chordal graphs. The author shows that the problem is polynomially solvable for two important subclasses of chordal graphs: strongly chordal graphs and undirected path graphs. Special structural properties of these classes of graphs are used to design an O(m log n) algorithm for strongly chordal graphs an \(O(n^ 4)\) algorithm for undirected path graphs.
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 4204393
zbMATH Keywords: dominating clique
zbMATH Keywords: chordal graphs
zbMATH Keywords: strongly chordal graphs
zbMATH Keywords: undirected path graphs
MaRDI profile type: Publication
cites work: Characterizations of totally balanced matrices
cites work: Q4099676
cites work: Q3351395
cites work: On domination problems for permutation and other graphs
cites work: Q3694712
cites work: Clustering and domination in perfect graphs
cites work: Dominating sets in perfect graphs
cites work: Dominating cliques in graphs
cites work: Characterizations of strongly chordal graphs
cites work: Q4198056
cites work: The intersection graphs of subtrees in trees are exactly the chordal graphs
cites work: A recognition algorithm for the intersection graphs of directed paths in directed trees
cites work: A recognition algorithm for the intersection graphs of paths in trees
cites work: Q3328583
cites work: The NP-completeness column: An ongoing guide
cites work: The NP-completeness column: an ongoing guide
cites work: Q3782805
cites work: Dominating cliques in chordal graphs
cites work: Intersection graphs of paths in a tree
cites work: Three Partition Refinement Algorithms
cites work: Interval graphs and related topics
Recommended article: Dominating cliques in chordal graphs
Recommended article: Q3782805
Recommended article: Dominating cliques in graphs
Recommended article: An approximation algorithm for clustering graphs with dominating diametral path
Recommended article: Characterizing and Computing the Structure of Clique Intersections in Strongly Chordal Graphs
Recommended article: Characterizing and computing the structure of clique intersections in strongly chordal graphs
Recommended article: Exact Algorithms for Dominating Clique Problems
Recommended article: Domination using induced cliques in graphs
Recommended article: Efficient algorithms with performance guarantees for some problems of finding several cliques in a complete undirected weighted graph
description: scientific article; zbMATH DE number 4204393