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...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L.
Formato: JOUR
Materias:
algorithms and data structures
efficient representation
graph theory
proper interval graphs
unit interval graphs
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_15710653_v35_nC_p247_Lin
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
Descripción
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.

Ejemplares similares