
The Library
Parallel O(log(n)) time edge-colouring of trees and Halin graphs
Tools
Gibbons, Alan (Alan M.), Israeli, Amos and Rytter, Wojciech (1987) Parallel O(log(n)) time edge-colouring of trees and Halin graphs. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)
|
PDF
WRAP_cs-rr-105.pdf - Other - Requires a PDF viewer. Download (9Mb) | Preview |
Abstract
We present parallel O(log(n))-time algorithms for optimal edge colouring of trees and Halin graphs with n processors on a a parallel random access machine without write conflicts (P-RAM). In the case of Halin graphs with a maximum degree of three, the colouring algorithm automatically finds every Hamiltonian cycle of the graph.
Item Type: | Report | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Library of Congress Subject Headings (LCSH): | Graph coloring, Parallel processing (Electronic computers) | ||||
Series Name: | Department of Computer Science research report | ||||
Publisher: | University of Warwick. Department of Computer Science | ||||
Official Date: | June 1987 | ||||
Dates: |
|
||||
Number: | Number 105 | ||||
DOI: | CS-RR-105 | ||||
Institution: | University of Warwick | ||||
Theses Department: | Department of Computer Science | ||||
Status: | Not Peer Reviewed | ||||
Publication Status: | Unpublished | ||||
Reuse Statement (publisher, data, author rights): | A.M. Gibbons, A. Israeli and W. Rytter, “Parallel O(log(n)) Time Edge-Colouring of Trees and Halin Graphs”, <i>Information Processing Letters</i> <b>27</b>(1), pp. 43-51 (1988) | ||||
Funder: | Mekhon Ṿaitsman le-madaʻ [Weizmann Institute of Science], National Science Foundation (U.S.) (NSF) | ||||
Grant number: | DCR-86-0636 (NSF) | ||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
![]() |
View Item |