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

DOI10.1016/0020-0190(88)90080-4MaRDI QIDQ1107328zbMATH OpenOpenAlexFDO

Authors A. Gibbons, Amos Israeli, Wojciech Rytter

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

treesHamiltonian cycleparallel computationPRAMHalin graphsedge-colouring

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)

Recommendations

• scientific article; zbMATH DE number 4047152
• A parallel algorithm for edge-coloring of graphs with edge-disjoint cycles
• scientific article; zbMATH DE number 4049082
• Fast parallel edge colouring of graphs.
• Publication:3484353

Cites work

• scientific article; zbMATH DE number 3853133 (Why is no real title available?)
• scientific article; zbMATH DE number 3878376 (Why is no real title available?)
• scientific article; zbMATH DE number 3968611 (Why is no real title available?)
• scientific article; zbMATH DE number 3654142 (Why is no real title available?)
• A fast parallel algorithm for routing in permutation networks
• Algorithms for Edge Coloring Bipartite Graphs and Multigraphs
• An Efficient Parallel Biconnectivity Algorithm
• Efficient Vertex- and Edge-Coloring of Outerplanar Graphs
• On the chromatic index of outerplanar graphs
• Parallel Algorithms in Graph Theory: Planarity Testing
• Parallelism in random access machines
• The NP-Completeness of Edge-Coloring

Cited in

(7)

• Parallel algorithms for a class of graphs generated recursively
• scientific article; zbMATH DE number 4047152 (Why is no real title available?)
• scientific article; zbMATH DE number 4155883 (Why is no real title available?)
• Optimally edge-colouring outerplanar graphs is in NC
• A parallel algorithm for edge-coloring of graphs with edge-disjoint cycles
• scientific article; zbMATH DE number 1759462 (Why is no real title available?)
• NC-algorithms for graphs with small treewidth

This page was built for publication: Parallel O(log n) time edge-colouring of trees and Halin graphs

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