Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs

DOI10.1016/0020-0190(88)90178-0zbMath0658.68079OpenAlexW1968285535MaRDI QIDQ1111390

Chin-Wen Ho, Richard Chia-Tung Lee

Publication date: 1988

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(88)90178-0

zbMATH Keywords

parallel algorithmsmaximal cliqueschordal graphsclique treeminimum coloringgraph separator

Mathematics Subject Classification ID

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

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, Selection of programme slots of television channels for giving advertisement: a graph theoretic approach, Minimum Average Distance Clique Trees, Distributed algorithms for maximum cliques, 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, Parallel computation of perfect elimination schemes using partition techniques on triangulated graphs, The maximum clique problem, An efficient algorithm to generate all maximal independent sets on trapezoid graphs, An Efficient Algorithm to Generate all Maximal Cliques on Trapezoid Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• On rigid circuit graphs
• Finding Euler tours in parallel
• Some parallel algorithms on interval graphs
• Chordal graph recognition is in NC
• A characterisation of rigid circuit graphs
• Incidence matrices and interval graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Tight Bounds on the Complexity of Parallel Sorting
• A Separator Theorem for Chordal Graphs
• An Efficient Parallel Biconnectivity Algorithm
• Computing connected components on parallel computers
• An O(logn) parallel connectivity algorithm