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

DOI10.1007/BFB0023483MaRDI QIDQ5048948zbMATH OpenFDO

Authors Elias Dahlhaus

Publication date 9 November 2022

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

Mathematics Subject Classification ID

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

Recommendations

• Efficient Parallel Algorithms for Chordal Graphs
• Fast Parallel Algorithms for Chordal Graphs
• An efficient representation of chordal graphs
• Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs
• NC algorithms for recognizing chordal graphs and k trees

Cites work

• scientific article; zbMATH DE number 4076453 (Why is no real title available?)
• A characterisation of rigid circuit graphs
• A linear-time algorithm for a special case of disjoint set union
• A parallel algorithm for computing Steiner trees in strongly chordal graphs
• A simple parallel tree contraction algorithm
• An O(logn) parallel connectivity algorithm
• Characterizations of strongly chordal graphs
• Degrees of acyclicity for hypergraphs and relational database schemes
• Domination, independent domination, and duality in strongly chordal graphs
• Nonredundant 1’s in $\Gamma $-Free Matrices
• Parallel algorithms for evaluating sequences of set-manipulation operations
• 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
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The parallel solution of domination problems on chordal and strongly chordal graphs
• Triangulated graphs and the elimination process

Cited in

(8)

• Minimal elimination ordering for graphs of bounded degree
• Fast Parallel Algorithms for Chordal Graphs
• An efficient representation of chordal graphs
• A parallel algorithm for computing Steiner trees in strongly chordal graphs
• An Implicit Representation of Chordal Comparabilty Graphs in Linear-Time
• The parallel solution of domination problems on chordal and strongly chordal graphs
• Counting clique trees and computing perfect elimination schemes in parallel
• scientific article; zbMATH DE number 4115994 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5048948)