Navegar

Colección

Datos Estadísticas

Artículo

Lin, M.C.; Soulignac, F.J.; Szwarcfiter, J.L. "Short Models for Unit Interval Graphs" (2009) Electronic Notes in Discrete Mathematics. 35(C):247-255
La versión final de este artículo es de uso interno. El editor solo permite incluir en el repositorio el artículo en su versión post-print. Por favor, si usted la posee enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

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.

Registro:

Documento: Artículo
Título:Short Models for Unit Interval Graphs
Autor:Lin, M.C.; Soulignac, F.J.; Szwarcfiter, J.L.
Filiación:Departamento de Computación, FCEN, Universidad de Buenos Aires, Buenos Aires, Argentina
Universidade Federal do Rio de Janeiro, Inst. de Matemática, NCE, Caixa Postal 2324, 20001-970 Rio de Janeiro, RJ, Brazil
Palabras clave:algorithms and data structures; efficient representation; graph theory; proper interval graphs; unit interval graphs
Año:2009
Volumen:35
Número:C
Página de inicio:247
Página de fin:255
DOI: http://dx.doi.org/10.1016/j.endm.2009.11.041
Título revista:Electronic Notes in Discrete Mathematics
Título revista abreviado:Electron. Notes Discrete Math.
ISSN:15710653
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v35_nC_p247_Lin

Referencias:

  • 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

Citas:

---------- APA ----------
Lin, M.C., Soulignac, F.J. & Szwarcfiter, J.L. (2009) . Short Models for Unit Interval Graphs. Electronic Notes in Discrete Mathematics, 35(C), 247-255.
http://dx.doi.org/10.1016/j.endm.2009.11.041
---------- CHICAGO ----------
Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L. "Short Models for Unit Interval Graphs" . Electronic Notes in Discrete Mathematics 35, no. C (2009) : 247-255.
http://dx.doi.org/10.1016/j.endm.2009.11.041
---------- MLA ----------
Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L. "Short Models for Unit Interval Graphs" . Electronic Notes in Discrete Mathematics, vol. 35, no. C, 2009, pp. 247-255.
http://dx.doi.org/10.1016/j.endm.2009.11.041
---------- VANCOUVER ----------
Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L. Short Models for Unit Interval Graphs. Electron. Notes Discrete Math. 2009;35(C):247-255.
http://dx.doi.org/10.1016/j.endm.2009.11.041