The Library
Parallel O(log(n)) time edge-colouring of trees and Halin graphs
Tools
Tools
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 > 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 | ||||
| Publisher Statement: | 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 |
Downloads
Downloads per month over past year
