A PARALLEL SOLUTION OF DOMINATION PROBLEMS ON CHORDAL AND STRONGLY CHORDAL GRAPHS

Authors
DAHLHAUS E DAMASCHKE P
Citation
E. Dahlhaus et P. Damaschke, A PARALLEL SOLUTION OF DOMINATION PROBLEMS ON CHORDAL AND STRONGLY CHORDAL GRAPHS, Discrete applied mathematics, 52(3), 1994, pp. 261-273
Citations number
32
Categorie Soggetti
Mathematics,Mathematics
Journal title
Discrete applied mathematics → ACNP
Volume
52
Issue
3
Year of publication
1994
Pages
261 - 273
Database
ISI
SICI code
Abstract
We present efficient parallel algorithms for the domination problem on strongly chordal graphs and related problems, such as the set cover p roblem for alpha-acyclic hypergraphs and the dominating clique problem for strongly chordal graphs. Moreover, we present an efficient parall el algorithm which checks, for any chordal graph, whether it has a dom inating clique.