Fast Parallel Algorithms for Chordal Graphs

DOI10.1137/0218023MaRDI QIDQ3825102zbMATH OpenOpenAlexFDO

Authors Joseph (Seffi) Naor, Moni Naor, Alejandro A. Schäffer

Publication date 1989

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

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

zbMATH Keywords

chordal graphsrecognitionfast parallel algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Recommendations

• Efficient 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
• Sequential and parallel algorithms on compactly represented chordal and strongly chordal graphs
• Parallel recognition algorithms for chordal-planar graphs and planar k-trees

Cited in

(23)

• An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph
• The parallel complexity of elimination ordering procedures
• A parallel algorithm to generate all maximal independent sets on permutation graphs
• scientific article; zbMATH DE number 4068310 (Why is no real title available?)
• Parallel algorithms for maximal cliques in circle graphs and unrestricted depth search
• An efficient algorithm to generate all maximal independent sets on trapezoid graphs
• Partitioning a chordal graph into transitive subgraphs for parallel sparse triangular solution
• Sequential and parallel algorithms on compactly represented chordal and strongly chordal graphs
• A parallel algorithm for minimum weighted colouring of triangulated graphs
• Parallel recognition algorithms for chordal-planar graphs and planar k-trees
• Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs
• Finding minimum height elimination trees for interval graphs in polynomial time
• Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach
• An Efficient Algorithm to Generate all Maximal Cliques on Trapezoid Graphs
• Distributed algorithms for maximum cliques
• Selection of programme slots of television channels for giving advertisement: a graph theoretic approach
• SCHEDULING INTERVAL ORDERS IN PARALLEL
• A parallel algorithm for computing Steiner trees in strongly chordal graphs
• NC algorithms for recognizing chordal graphs and k trees
• Clique tree generalization and new subclasses of chordal graphs
• The parallel solution of domination problems on chordal and strongly chordal graphs
• Counting clique trees and computing perfect elimination schemes in parallel
• Induced matchings in intersection graphs.

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

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