Efficient Parallel Algorithms for Chordal Graphs

DOI10.1137/S0097539789166880MaRDI QIDQ4895831zbMATH OpenFDO

Authors Philip N. Klein

Publication date 16 October 1996

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539789166880

zbMATH Keywords

chordal graphsparallel algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Distributed algorithms (68W15)

Recommendations

• Fast Parallel Algorithms for 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
• Parallel algorithms on interval graphs
• Sequential and parallel algorithms on compactly represented chordal and strongly chordal graphs

Cited in

(26)

• Laminar structure of ptolemaic graphs with applications
• Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs
• Counting clique trees and computing perfect elimination schemes in parallel
• Efficient parallel algorithms for graph problems
• Partitioning a chordal graph into transitive subgraphs for parallel sparse triangular solution
• A parallel algorithm for computing Steiner trees in strongly chordal graphs
• The parallel solution of domination problems on chordal and strongly chordal graphs
• Finding minimum height elimination trees for interval graphs in polynomial time
• Biconvex graphs: Ordering and algorithms
• The QAP-polytope and the graph isomorphism problem
• Parallel recognition algorithms for chordal-planar graphs and planar k-trees
• Efficient parallel algorithm to compute a doubly perfect elimination ordering of a doubly chordal graph
• Parallel algorithms for maximal cliques in circle graphs and unrestricted depth search
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• scientific article; zbMATH DE number 3972201 (Why is no real title available?)
• NC algorithms for recognizing chordal graphs and k trees
• Fast Parallel Algorithms for Chordal Graphs
• scientific article; zbMATH DE number 1533813 (Why is no real title available?)
• Interval graph representation with given interval and intersection lengths
• Sequential and parallel algorithms on compactly represented chordal and strongly chordal graphs
• Chordal graphs and their clique graphs
• The parallel complexity of elimination ordering procedures
• I/O-efficient algorithms for graphs of bounded treewidth
• Recognizing and representing proper interval graphs in parallel using merging and sorting
• Counting the number of independent sets in chordal graphs
• A parallel algorithm for generating bicompatible elimination orderings of proper interval graphs

This page was built for publication: Efficient Parallel Algorithms for Chordal Graphs

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