×

A parallel algorithm for edge-coloring of graphs with edge-disjoint cycles. (English) Zbl 0769.68033

Summary: We present a new linear algorithm for coloring the edges of a tree. Although this is not the first linear algorithm for the problem, our algorithm unlike the existing ones can be parallelized directly. The parallelization is obtained by showing that edge-coloring can be carried out using tree contraction. Hence, it can be done in \(O(\log n)\) time using \(n/\log n\) processors on the EREW PRAM. When the problem is extended to one of coloring the edges of a graph with edge-disjont cycles, the said algorithm for trees can be extended very easily without increasing the resource requirement.

MSC:

68W15 Distributed algorithms
68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abrahamson, K.; Dadoun, N.; Kirkpatrick, D. G.; Przytycka, T., A simple parallel tree contraction algorithm, J. Algorithms, 10, 287-302 (1989) · Zbl 0681.68085
[2] Anderson, R. J.; Miller, G. L., Deterministic parallel list ranking, Algorithmica, 6, 859-868 (1991) · Zbl 0732.68045
[3] Gabow, H., Using Euler partitions to edge color bipartite multigraphs, Internat. J. Comput. Inform. Sci., 5, 345-355 (1976) · Zbl 0411.05039
[4] Garey, M. R.; Johnson, D., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco, CA · Zbl 0411.68039
[5] Gibbons, A. M.; Israeli, A.; Rytter, W., Parallel O(log \(n)\) time edge-colouring of trees and Halin graphs, Inform. Process. Lett., 27, 43-51 (1988) · Zbl 0652.68084
[6] Hagerup, T.; Shen, H., Improved nonconservative sequential and parallel integer sorting, Inform. Process. Lett., 36, 57-63 (1990) · Zbl 0704.68028
[7] Miller, G. L.; Reif, J. H., Parallel tree contraction and its applications, (Proc. 26th Ann. Symp. on Foundations of Computer Science. Proc. 26th Ann. Symp. on Foundations of Computer Science, New York (1985)), 478-489
[8] Mitchell, S. L.; Cockayne, E. J.; Hedetniemi, S. T., Linear algorithms on recursive representation of trees, J. Comput. System Sci., 18, 76-85 (1979) · Zbl 0398.68008
[9] Mitchell, S. L.; Hedetniemi, S. T., Linear algorithms for edge-coloring trees and unicyclic graphs, Inform. Process. Lett., 9, 110-112 (1979) · Zbl 0415.68030
[10] Vizing, V., On the estimate of the chromatic number of a graph, Diskret. Analiz., 3, 25-30 (1964)
[11] Wyllie, J. C., The complexity of parallel computation, (Ph.D. Thesis (1979), Cornell University: Cornell University Ithaca, NY)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.