Sequential and parallel algorithms on compactly represented chordal and strongly chordal graphs

DOI10.1007/BFb0023483zbMath1498.68199MaRDI QIDQ5048948

Elias Dahlhaus

Publication date: 9 November 2022

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Related Items (1)

Minimal elimination ordering for graphs of bounded degree

Cites Work

• Unnamed Item
• Domination, independent domination, and duality in strongly chordal graphs
• Characterizations of strongly chordal graphs
• A linear-time algorithm for a special case of disjoint set union
• A parallel algorithm for computing Steiner trees in strongly chordal graphs
• The parallel solution of domination problems on chordal and 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
• Degrees of acyclicity for hypergraphs and relational database schemes
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Steiner trees, connected domination and strongly chordal graphs
• An O(logn) parallel connectivity algorithm
• Parallel algorithms for evaluating sequences of set-manipulation operations
• A simple parallel tree contraction algorithm
• Nonredundant 1’s in $\Gamma $-Free Matrices

This page was built for publication: Sequential and parallel algorithms on compactly represented chordal and strongly chordal graphs