Parallel O(log n) time edge-colouring of trees and Halin graphs

DOI10.1016/0020-0190(88)90080-4zbMath0652.68084OpenAlexW2042837269MaRDI QIDQ1107328

Alan M. Gibbons, Wojciech Rytter, Amos Israeli

Publication date: 1988

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

Full work available at URL: http://wrap.warwick.ac.uk/60801/12/WRAP_cs-rr-105.pdf

zbMATH Keywords

parallel computationedge-colouringHamiltonian cycletreesPRAMHalin 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)

Related Items

NC-algorithms for graphs with small treewidth ⋮ Optimally edge-colouring outerplanar graphs is in NC ⋮ A parallel algorithm for edge-coloring of graphs with edge-disjoint cycles ⋮ Parallel algorithms for a class of graphs generated recursively

Cites Work

• On the chromatic index of outerplanar graphs
• An Efficient Parallel Biconnectivity Algorithm
• Efficient Vertex- and Edge-Coloring of Outerplanar Graphs
• A fast parallel algorithm for routing in permutation networks
• The NP-Completeness of Edge-Coloring
• Algorithms for Edge Coloring Bipartite Graphs and Multigraphs
• Parallel Algorithms in Graph Theory: Planarity Testing
• Parallelism in random access machines
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item