The parallel solution of domination problems on chordal and strongly chordal graphs
DOI10.1016/0166-218X(94)90145-7zbMATH Open0803.05048MaRDI QIDQ1331893FDOQ1331893
Authors: Elias Dahlhaus, Peter Damaschke 
Publication date: 27 September 1994
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Recommendations
- A linear-time algorithm for paired-domination problem in strongly chordal graphs
- Sequential and parallel algorithms on compactly represented chordal and strongly chordal graphs
- A simple linear time algorithm for the domatic partition problem on strongly chordal graphs
- Parallel algorithms for the domination problems in trapezoid graphs
- Parameterized dominating set problem in chordal graphs: Complexity and lower bound
- scientific article; zbMATH DE number 4053037
- A linear-time algorithm for semitotal domination in strongly chordal graphs
- Efficient Parallel Algorithms for Chordal Graphs
- A parallel algorithm for computing Steiner trees in strongly chordal graphs
parallel algorithmdominating set problemhypergraphchordal graphstrongly chordal graphsdominating cliquecover problem
Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Hypergraphs (05C65) Structural characterization of families of graphs (05C75) Distributed algorithms (68W15) Graph theory (05C99)
Cites Work
- On rigid circuit graphs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Characterizations of strongly chordal graphs
- Triangulated graphs and the elimination process
- On the Desirability of Acyclic Database Schemes
- Title not available (Why is that?)
- An Efficient Parallel Biconnectivity Algorithm
- Domination, independent domination, and duality in strongly chordal graphs
- Parallelism in random access machines
- Clique graphs and Helly graphs
- Title not available (Why is that?)
- Steiner trees, connected domination and strongly chordal graphs
- Graphs whose neighborhoods have no special cycles
- Degrees of acyclicity for hypergraphs and relational database schemes
- A characterisation of rigid circuit graphs
- On hypergraph acyclicity and graph chordality
- An O(logn) parallel connectivity algorithm
- Title not available (Why is that?)
- Computing connected components on parallel computers
- A simple parallel tree contraction algorithm
- Implementation of simultaneous memory address access in models that forbid it
- Title not available (Why is that?)
- Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs
- Fast Parallel Algorithms for Chordal Graphs
- A parallel algorithm for computing Steiner trees in strongly chordal graphs
Cited In (4)
This page was built for publication: The parallel solution of domination problems on chordal and strongly chordal graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1331893)
