Optimal parallel colouring algorithms for totally decomposable graphs

DOI10.1080/00207169308804183MaRDI QIDQ4323714zbMATH OpenOpenAlexFDO

Authors 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 rankingtotally decomposable graphstree contraction

Mathematics Subject Classification ID

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

Recommendations

• Computational Science - ICCS 2004
• scientific article; zbMATH DE number 4047152
• Optimal parallel algorithms for coloring bounded degree graphs and finding maximal independent sets in rooted trees
• scientific article; zbMATH DE number 19774
• Optimal parallel 3-coloring algorithm for rooted trees and its applications

Cites work

• A simple parallel tree contraction algorithm
• 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
• Complement reducible graphs
• Efficient parallel algorithms for graph problems
• scientific article; zbMATH DE number 4011928 (Why is no real title available?)
• On Finding Lowest Common Ancestors: Simplification and Parallelization

Cited in

(5)

• A parallel algorithm for solving the coloring problem on trapezoid graphs
• scientific article; zbMATH DE number 4047152 (Why is no real title available?)
• scientific article; zbMATH DE number 2090688 (Why is no real title available?)
• scientific article; zbMATH DE number 7566051 (Why is no real title available?)
• Computational Science - ICCS 2004

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

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