| Author | dc.contributor.author | Durán Maggiolo, Guillermo | |
| Author | dc.contributor.author | Gravano, Agustín | es_CL |
| Author | dc.contributor.author | McConnell, Ross M. | es_CL |
| Author | dc.contributor.author | Spinrad, Jeremy | es_CL |
| Author | dc.contributor.author | Tucker, Alan | es_CL |
| Admission date | dc.date.accessioned | 2009-03-30T18:12:10Z | |
| Available date | dc.date.available | 2009-03-30T18:12:10Z | |
| Publication date | dc.date.issued | 2006-01 | |
| Cita de ítem | dc.identifier.citation | JOURNAL OF ALGORITHMS Volume: 58 Issue: 1 Pages: 67-78 Published: JAN 2006 | en |
| Identifier | dc.identifier.issn | 0196-6774 | |
| Identifier | dc.identifier.uri | https://repositorio.uchile.cl/handle/2250/124839 | |
| Abstract | dc.description.abstract | We present an efficient algorithm for recognizing unit circular-arc (UCA) graphs, based on a characterization theorem for UCA graphs proved by Tucker in the seventies. Given a proper circular-arc (PCA) graph G, the algorithm starts from a PCA model for G, removes all its circle-covering pairs of arcs and determines whether G is a UCA graph. We also give an O(N) time bound for Tucker's 3/2-approximation algorithm for coloring circular-arc graphs with N vertices, when a circular-arc model is given. | en |
| Lenguage | dc.language.iso | en | en |
| Publisher | dc.publisher | ACADEMIC PRESS INC ELSEVIER SCIENCE | en |
| Keywords | dc.subject | ALGORITHM | en |
| Título | dc.title | Polynomial time recognition of unit circular-arc graphs | en |
| Document type | dc.type | Artículo de revista | |
