An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph.
| dc.contributor.author | Masuda, Sumio | en_US |
| dc.contributor.author | Nakajima, K. | en_US |
| dc.contributor.department | ISR | en_US |
| dc.date.accessioned | 2007-05-23T09:35:53Z | |
| dc.date.available | 2007-05-23T09:35:53Z | |
| dc.date.issued | 1986 | en_US |
| dc.description.abstract | A new algorithm is presented for finding a maximum independent set of a circular-arc graph. When the graph is given in the form of a family of n arcs, our algorithm requires only O(n log n) time and O(n) space. Furthermore, if the endpoints of the arcs are already sorted, it runs in O(n) time. This algorithm is time- and space-optimal to within a constant factor. | en_US |
| dc.format.extent | 691979 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.identifier.uri | http://hdl.handle.net/1903/4492 | |
| dc.language.iso | en_US | en_US |
| dc.relation.ispartofseries | ISR; TR 1986-68 | en_US |
| dc.title | An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph. | en_US |
| dc.type | Technical Report | en_US |
Files
Original bundle
1 - 1 of 1