Optimally edge-colouring outerplanar graphs is in NC

DOI10.1016/0304-3975(90)90051-IzbMath0694.68033MaRDI QIDQ909461

Wojciech Rytter, Alan M. Gibbons

Publication date: 1990

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

edge-colouringouterplanar graphsP-RAM

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Linear algorithms for edge-coloring trees and unicyclic graphs
• Parallel O(log n) time edge-colouring of trees and Halin graphs
• On the chromatic index of outerplanar graphs
• An Efficient Parallel Biconnectivity Algorithm
• Efficient Vertex- and Edge-Coloring of Outerplanar Graphs
• Efficient parallel algorithms for edge coloring problems
• A fast parallel algorithm for routing in permutation networks
• The NP-Completeness of Edge-Coloring
• Algorithms for Edge Coloring Bipartite Graphs and Multigraphs
• Parallelism in random access machines

This page was built for publication: Optimally edge-colouring outerplanar graphs is in NC