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í |
| Sumario: | 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. |
|---|---|
| Bibliografía: | Bogart, K.P., West, D.B., A short proof that "proper = unit" (1999) Discrete Math., 201 (1-3), pp. 21-23 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 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 Gardi, F., The Roberts characterization of proper and unit interval graphs (2007) Discrete Math., 307 (22), pp. 2906-2908 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 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) Spinrad, J.P., (2003) Efficient graph representations, , American Mathematical Society |
| ISSN: | 15710653 |
| DOI: | 10.1016/j.endm.2009.11.041 |