Fast Parallel Algorithms for Chordal Graphs

DOI10.1137/0218023zbMath0672.05055OpenAlexW2072122885MaRDI QIDQ3825102

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

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

fast parallel algorithmsrecognitionchordal graphs

Mathematics Subject Classification ID

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

Related Items

The parallel solution of domination problems on chordal and strongly chordal graphs, An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph, Clique tree generalization and new subclasses of chordal graphs, SCHEDULING INTERVAL ORDERS IN PARALLEL, Selection of programme slots of television channels for giving advertisement: a graph theoretic approach, A width parameter useful for chordal and co-comparability graphs, Distributed algorithms for maximum cliques, Induced matchings in intersection graphs., A parallel algorithm for minimum weighted colouring of triangulated graphs, A parallel algorithm to generate all maximal independent sets on permutation graphs, Parallel Algorithms for Maximal Cliques in Circle Graphs and Unrestricted Depth Search, Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach, Counting clique trees and computing perfect elimination schemes in parallel, An efficient algorithm to generate all maximal independent sets on trapezoid graphs, An Efficient Algorithm to Generate all Maximal Cliques on Trapezoid Graphs