The Library
Optimally edge-colouring outerplanar graphs is in NC
Tools
Tools
Tools
Gibbons, Alan (Alan M.) and Rytter, Wojciech (1989) Optimally edge-colouring outerplanar graphs is in NC. Coventry, UK: University of Warwick. Department of Computer Science. (Department of Computer Science Research Report). (Unpublished)
|
PDF
WRAP_cs-rr-135.pdf - Requires a PDF viewer. Download (9Mb) | Preview |
Abstract
We prove that every outerplanar graph can be optimally edge-coloured in polylogarithmic time using a polynomial number of processors on a parallel random access machine without write conflicts (P-RAM).
| 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): | 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: | January 1989 | ||||
| Dates: |
|
||||
| Number: | Number 135 | ||||
| Number of Pages: | 12 | ||||
| DOI: | CS-RR-135 | ||||
| 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 and W. Rytter, “Optimally Edge-Colouring Outerplanar Graphs is in NC”, <i>Theoretical Computer Science</i> <b>71</b>, pp. 401-411 (1990) | ||||
| 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
