The parallel solution of domination problems on chordal and strongly chordal graphs
From MaRDI portal
Publication:1331893
DOI10.1016/0166-218X(94)90145-7zbMath0803.05048MaRDI QIDQ1331893
Peter Damaschke, Elias Dahlhaus
Publication date: 27 September 1994
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
hypergraphparallel algorithmchordal graphdominating set problemstrongly chordal graphsdominating cliquecover problem
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Hypergraphs (05C65) Paths and cycles (05C38) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (05C99) Distributed algorithms (68W15)
Related Items
A parallel algorithm for computing Steiner trees in strongly chordal graphs, Sequential and parallel algorithms on compactly represented chordal and strongly chordal graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On rigid circuit graphs
- Domination, independent domination, and duality in strongly chordal graphs
- Graphs whose neighborhoods have no special cycles
- Clique graphs and Helly graphs
- Characterizations of strongly chordal graphs
- Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs
- On hypergraph acyclicity and graph chordality
- A parallel algorithm for computing Steiner trees in strongly chordal graphs
- A characterisation of rigid circuit graphs
- Triangulated graphs and the elimination process
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- On the Desirability of Acyclic Database Schemes
- Degrees of acyclicity for hypergraphs and relational database schemes
- An Efficient Parallel Biconnectivity Algorithm
- Steiner trees, connected domination and strongly chordal graphs
- Fast Parallel Algorithms for Chordal Graphs
- Computing connected components on parallel computers
- An O(logn) parallel connectivity algorithm
- A simple parallel tree contraction algorithm
- Implementation of simultaneous memory address access in models that forbid it
- Parallelism in random access machines
