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

DOI10.1007/BFB0023483zbMATH Open1498.68199MaRDI QIDQ5048948FDOQ5048948

Authors: Elias Dahlhaus 

Publication date: 9 November 2022

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

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

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)

Cites Work

• A linear-time algorithm for a special case of disjoint set union
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Characterizations of strongly chordal graphs
• Triangulated graphs and the elimination process
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Domination, independent domination, and duality in strongly chordal graphs
• Steiner trees, connected domination and strongly chordal graphs
• Degrees of acyclicity for hypergraphs and relational database schemes
• A characterisation of rigid circuit graphs
• An O(logn) parallel connectivity algorithm
• Nonredundant 1’s in $\Gamma $-Free Matrices
• A simple parallel tree contraction algorithm
• Title not available (Why is that?)
• The parallel solution of domination problems on chordal and strongly chordal graphs
• A parallel algorithm for computing Steiner trees in strongly chordal graphs
• Parallel algorithms for evaluating sequences of set-manipulation operations

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
• Title not available (Why is that?)

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)