Optimal parallel colouring algorithms for totally decomposable graphs

DOI10.1080/00207169308804183zbMath0813.68113OpenAlexW2064987152MaRDI QIDQ4323714

Rong Lin, Stephan Olariu

Publication date: 20 February 1995

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207169308804183

zbMATH Keywords

list rankingtree contractiontotally decomposable graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Distributed algorithms (68W15)

Cites Work

• Unnamed Item
• Complement reducible graphs
• Efficient parallel algorithms for graph problems
• An Efficient Parallel Biconnectivity Algorithm
• Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time
• Binary tree algebraic computation and parallel algorithms for simple graphs
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• A simple parallel tree contraction algorithm

This page was built for publication: Optimal parallel colouring algorithms for totally decomposable graphs