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

DOI10.1016/0012-365X(90)90363-MzbMath0729.05046MaRDI QIDQ805638

Dieter Kratsch

Publication date: 1990

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

chordal graphsstrongly chordal graphsundirected path graphsdominating clique

Mathematics Subject Classification ID

Graph theory (05C99)

Related Items (13)

Dominating cliques in distance-hereditary graphs ⋮ \(r\)-dominating cliques in graphs with hypertree structure ⋮ A note on \(r\)-dominating cliques ⋮ A linear-time algorithm for semitotal domination in strongly chordal graphs ⋮ Complexity of distance paired-domination problem in graphs ⋮ Weighted connected \(k\)-domination and weighted \(k\)-dominating clique in distance-hereditary graphs ⋮ A linear-time algorithm for paired-domination problem in strongly chordal graphs ⋮ Semicomplete absorbent sets in digraphs ⋮ Minimum partition of an independence system into independent sets ⋮ Revising Johnson's table for the 21st century ⋮ Bibliography on domination in graphs and some basic definitions of domination parameters ⋮ Dominating cliques in chordal graphs ⋮ On connected dominating sets of restricted diameter

Cites Work

• Characterizations of strongly chordal graphs
• Interval graphs and related topics
• Clustering and domination in perfect graphs
• Intersection graphs of paths in a tree
• On domination problems for permutation and other graphs
• Dominating sets in perfect graphs
• A recognition algorithm for the intersection graphs of directed paths in directed trees
• A recognition algorithm for the intersection graphs of paths in trees
• Dominating cliques in chordal graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Characterizations of totally balanced matrices
• The NP-completeness column: an ongoing guide
• Three Partition Refinement Algorithms
• The NP-completeness column: An ongoing guide
• Dominating cliques in graphs
• The NP-completeness column: An ongoing guide
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs