Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs (Q805638)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4204393
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs |
scientific article; zbMATH DE number 4204393 |
Statements
Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs (English)
0 references
1990
0 references
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.
0 references
dominating clique
0 references
chordal graphs
0 references
strongly chordal graphs
0 references
undirected path graphs
0 references
0 references
0 references
0 references
0 references
0.88874644
0 references
0.8857748
0 references
0.8857746
0 references
0.8856078
0 references
0.8843403
0 references
