Short Models for Unit Interval Graphs
We present one more proof of the fact that the class of proper interval graphs is precisely the class of unit interval graphs. The proof leads to a new and efficient O (n) time and space algorithm that transforms a proper interval model of the graph into a unit model, where all the extremes are inte...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | , |
| Formato: | Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
2009
|
| Acceso en línea: | Registro en Scopus DOI Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 04603caa a22005537a 4500 | ||
|---|---|---|---|
| 001 | PAPER-8317 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518203807.0 | ||
| 008 | 190411s2009 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-70949092198 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 100 | 1 | |a Lin, M.C. | |
| 245 | 1 | 0 | |a Short Models for Unit Interval Graphs |
| 260 | |c 2009 | ||
| 270 | 1 | 0 | |m Lin, M.C.; Departamento de Computación, FCEN, Universidad de Buenos Aires, Buenos Aires, Argentina; email: oscarlin@dc.uba.ar |
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a Bogart, K.P., West, D.B., A short proof that "proper = unit" (1999) Discrete Math., 201 (1-3), pp. 21-23 | ||
| 504 | |a Corneil, D.G., A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs (2004) Discrete Appl. Math., 138 (3), pp. 371-379 | ||
| 504 | |a Corneil, D.G., Kim, H., Natarajan, S., Olariu, S., Sprague, A.P., Simple linear time recognition of unit interval graphs (1995) Inform. Process. Lett., 55 (2), pp. 99-104 | ||
| 504 | |a Gardi, F., The Roberts characterization of proper and unit interval graphs (2007) Discrete Math., 307 (22), pp. 2906-2908 | ||
| 504 | |a Lin, M.C., Rautenbach, D., Soulignac, F.J., Szwarcfiter, J.L., Powers of Cycles, Powers of Paths and Distance Graphs (2008), Submitted; Lin, M.C., Szwarcfiter, J.L., Unit circular-arc graph representations and feasible circulations (2008) SIAM J. Discrete Math., 22, pp. 409-423 | ||
| 504 | |a Roberts, F.S., Indifference graphs (1969) Proof Techniques in Graph Theory, pp. 139-146. , (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968) | ||
| 504 | |a Spinrad, J.P., (2003) Efficient graph representations, , American Mathematical Society | ||
| 520 | 3 | |a We present one more proof of the fact that the class of proper interval graphs is precisely the class of unit interval graphs. The proof leads to a new and efficient O (n) time and space algorithm that transforms a proper interval model of the graph into a unit model, where all the extremes are integers in the range 0 to O (n2), solving a problem posed by Gardi (Discrete Math., 307 (22), 2906-2908, 2007). © 2009 Elsevier B.V. All rights reserved. |l eng | |
| 536 | |a Detalles de la financiación: Fundação Carlos Chagas Filho de Amparo à Pesquisa do Estado do Rio de Janeiro | ||
| 536 | |a Detalles de la financiación: Conselho Nacional de Desenvolvimento Científico e Tecnológico, CNPq | ||
| 536 | |a Detalles de la financiación: 1562 | ||
| 536 | |a Detalles de la financiación: Fundação Carlos Chagas Filho de Amparo à Pesquisa do Estado do Rio de Janeiro | ||
| 536 | |a Detalles de la financiación: Secretaría de Ciencia y Técnica, Universidad de Buenos Aires, X456, X143 | ||
| 536 | |a Detalles de la financiación: Conselho Nacional de Desenvolvimento Científico e Tecnológico, CNPq | ||
| 536 | |a Detalles de la financiación: 1 Partially supported by UBACyT Grants X456 and X143, and PICT ANPCyT Grant 1562. 2 Partially supported by UBACyT Grant X456, PICT ANPCyT Grant 1562 and by a grant of the YPF Foundation. 3 Partially supported by the Conselho Nacional de Desenvolvimento Científico e Tec-nológico, CNPq, and Fundac¸ão de Amparo à Pesquisa do Estado do Rio de Janeiro, FAPERJ, Brasil. | ||
| 593 | |a Departamento de Computación, FCEN, Universidad de Buenos Aires, Buenos Aires, Argentina | ||
| 593 | |a Universidade Federal do Rio de Janeiro, Inst. de Matemática, NCE, Caixa Postal 2324, 20001-970 Rio de Janeiro, RJ, Brazil | ||
| 690 | 1 | 0 | |a ALGORITHMS AND DATA STRUCTURES |
| 690 | 1 | 0 | |a EFFICIENT REPRESENTATION |
| 690 | 1 | 0 | |a GRAPH THEORY |
| 690 | 1 | 0 | |a PROPER INTERVAL GRAPHS |
| 690 | 1 | 0 | |a UNIT INTERVAL GRAPHS |
| 700 | 1 | |a Soulignac, F.J. | |
| 700 | 1 | |a Szwarcfiter, J.L. | |
| 773 | 0 | |d 2009 |g v. 35 |h pp. 247-255 |k n. C |p Electron. Notes Discrete Math. |x 15710653 |t Electronic Notes in Discrete Mathematics | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-70949092198&doi=10.1016%2fj.endm.2009.11.041&partnerID=40&md5=251d36a5216e9994c17568f6f219dcac |y Registro en Scopus |
| 856 | 4 | 0 | |u https://doi.org/10.1016/j.endm.2009.11.041 |y DOI |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_15710653_v35_nC_p247_Lin |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v35_nC_p247_Lin |y Registro en la Biblioteca Digital |
| 961 | |a paper_15710653_v35_nC_p247_Lin |b paper |c PE | ||
| 962 | |a info:eu-repo/semantics/article |a info:ar-repo/semantics/artículo |b info:eu-repo/semantics/publishedVersion | ||
| 963 | |a VARI | ||
| 999 | |c 69270 | ||