The Library
Fast parallel algorithms for vertex and edge colouring of Halin graphs
Tools
Tools
Tools
Gibbons, Alan (Alan M.) and Rytter, Wojciech (1986) Fast parallel algorithms for vertex and edge colouring of Halin graphs. Coventry, UK: University of Warwick. Department of Computer Science. (Department of Computer Science Research Report). (Unpublished)
|
PDF
WRAP_cs-rr-083.pdf - Other - Requires a PDF viewer. Download (711Kb) | Preview |
Abstract
We show that every Halin graph can be optimally edge-coloured or optimally vertex-coloured in polylog time using a polynomial number of processors on a parallel random access machine without write conflicts (P-RAM). Our algorithm is designed using the tree-structure of Halin graphs which allows an application of the Divide and Conquer technique in a parallel setting.
| Item Type: | Report | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Parallel algorithms, Graph theory | ||||
| Series Name: | Department of Computer Science Research Report | ||||
| Publisher: | University of Warwick. Department of Computer Science | ||||
| Place of Publication: | Coventry, UK | ||||
| Official Date: | October 1986 | ||||
| Dates: |
|
||||
| Number: | Number 83 | ||||
| Number of Pages: | 8 | ||||
| DOI: | CS-RR-083 | ||||
| Institution: | University of Warwick | ||||
| Theses Department: | Department of Computer Science | ||||
| Status: | Not Peer Reviewed | ||||
| Publication Status: | Unpublished | ||||
| 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
