DocumentCode :
3204296
Title :
A near-optimal parallel algorithm for edge-coloring outerplanar graphs
Author :
Caspi, Yuval ; Dekel, Eliezer
Author_Institution :
Comput. Sci. Program, Texas Univ., Dallas, Richardson, TX, USA
fYear :
1992
fDate :
23-26 Mar 1992
Firstpage :
262
Lastpage :
266
Abstract :
The article presents a parallel EREW PRAM algorithm that runs in O(log2n) time using n/logn processors to optimally color the edges of an outerplanar graph. The algorithm improves the best known algorithm in both time, and number of processors. This more efficient algorithm is a result of a new approach for solving the problem. Also presented is a parallel EREW PRAM algorithm that runs in O(logn) using n/logn processors for finding a maximal matching in outerplanar graphs
Keywords :
computational complexity; graph colouring; parallel algorithms; edge-coloring; maximal matching; outerplanar graphs; parallel EREW PRAM algorithm; Color; Computational modeling; Computer science; Concurrent computing; Parallel algorithms; Phase change random access memory; Polynomials; Read-write memory; Tree graphs;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel Processing Symposium, 1992. Proceedings., Sixth International
Conference_Location :
Beverly Hills, CA
Print_ISBN :
0-8186-2672-0
Type :
conf
DOI :
10.1109/IPPS.1992.223035
Filename :
223035
Link To Document :
https://search.ricest.ac.ir/dl/search/defaultta.aspx?DTC=49&DC=3204296
بازگشت