The parallel solution of domination problems on chordal and strongly chordal graphs
type: Item
instance of: scholarly article
title: The parallel solution of domination problems on chordal and strongly chordal graphs
zbMATH Open document ID: 0803.05048
DOI: 10.1016/0166-218X(94)90145-7
author: Elias Dahlhaus
author: Peter Damaschke
published in: Discrete Applied Mathematics
publication date: 1994-09-27T00:00:00Z
review text: This paper discusses the problem of the existence of a dominating clique in a chordal graph. The equivalence of the dominating set problem and the minimum dominating clique problem for strongly chordal graphs has also been proved. Further, it has been proved that both problems are equivalent to the cover problem viz. the problem of finding a minimum subset of the hyperedge set that covers all vertices of a given \(\beta\)- acyclic hypergraph (the class of \(\beta\)-acyclic hypergraphs corresponds to the class of maximal clique sets of strongly chordal graphs). Finally, an efficient parallel algorithm for the cover problem for \(\alpha\)- acyclic hypergraphs which includes also an efficient parallel algorithm for the domination problems has been presented.
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 68W15
zbMATH DE Number: 626251
zbMATH Keywords: dominating clique
zbMATH Keywords: chordal graph
zbMATH Keywords: dominating set problem
zbMATH Keywords: strongly chordal graphs
zbMATH Keywords: cover problem
zbMATH Keywords: hypergraph
zbMATH Keywords: parallel algorithm
reviewed by: Bai Kishan Dass
MaRDI profile type: Publication
cites work: A simple parallel tree contraction algorithm
cites work: Q3948568
cites work: Clique graphs and Helly graphs
cites work: On the Desirability of Acyclic Database Schemes
cites work: Graphs whose neighborhoods have no special cycles
cites work: Q3879274
cites work: A characterisation of rigid circuit graphs
cites work: A parallel algorithm for computing Steiner trees in strongly chordal graphs
cites work: On hypergraph acyclicity and graph chordality
cites work: On rigid circuit graphs
cites work: Degrees of acyclicity for hypergraphs and relational database schemes
cites work: Characterizations of strongly chordal graphs
cites work: Domination, independent domination, and duality in strongly chordal graphs
cites work: Parallelism in random access machines
cites work: The intersection graphs of subtrees in trees are exactly the chordal graphs
cites work: Computing connected components on parallel computers
cites work: Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs
cites work: Q4385522
cites work: Q3782805
cites work: Fast Parallel Algorithms for Chordal Graphs
cites work: Triangulated graphs and the elimination process
cites work: An O(logn) parallel connectivity algorithm
cites work: An Efficient Parallel Biconnectivity Algorithm
cites work: Implementation of simultaneous memory address access in models that forbid it
cites work: Steiner trees, connected domination and strongly chordal graphs
Recommended article: A linear-time algorithm for paired-domination problem in strongly chordal graphs
Recommended article: Sequential and parallel algorithms on compactly represented chordal and strongly chordal graphs
Recommended article: A simple linear time algorithm for the domatic partition problem on strongly chordal graphs
Recommended article: Parallel algorithms for the domination problems in trapezoid graphs
Recommended article: Parameterized dominating set problem in chordal graphs: Complexity and lower bound
Recommended article: Q3789082
Recommended article: A linear-time algorithm for semitotal domination in strongly chordal graphs
Recommended article: Efficient Parallel Algorithms for Chordal Graphs
Recommended article: A parallel algorithm for computing Steiner trees in strongly chordal graphs
description: scientific article; zbMATH DE number 626251