scientific article; zbMATH DE number 4047152
From MaRDI portal
Publication:3783598
[For the entire collection see Zbl 0633.00025.] We show that every Halin and every outerplanar graph can be optimally edge-coloured in polylog time using a polynomial number of processors on a parallel random access machine without write conflicts (P-RAM). Our algorithms are designed using the divide and conquer technique in a parallel setting.
Recommendations
- A parallel algorithm for edge-coloring partial k-trees
- Fast parallel edge colouring of graphs.
- scientific article; zbMATH DE number 4076639
- scientific article; zbMATH DE number 4049082
- Efficient parallel algorithms for edge coloring problems
- Very fast parallel algorithms for approximate edge coloring
- Parallel O(log n) time edge-colouring of trees and Halin graphs
- Optimal parallel colouring algorithms for totally decomposable graphs
- Parallel algorithms for the edge-coloring and edge-coloring update problems
- Optimal parallel algorithms for coloring bounded degree graphs and finding maximal independent sets in rooted trees
Cited in
(10)- Parallel O(log n) time edge-colouring of trees and Halin graphs
- Optimal parallel 3-coloring algorithm for rooted trees and its applications
- A parallel algorithm for edge-coloring of graphs with edge-disjoint cycles
- Fast parallel edge colouring of graphs.
- scientific article; zbMATH DE number 4049082 (Why is no real title available?)
- A fast parallel algorithm to color a graph with Δ colors
- Optimal parallel colouring algorithms for totally decomposable graphs
- Parallel edge coloring of a tree on a mesh connected computer
- Very fast parallel algorithms for approximate edge coloring
- Optimally edge-colouring outerplanar graphs is in NC
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3783598)