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, Min Chih, Soulignac, Francisco Juan
Publicado: 2009
Materias:
algorithms and data structures
efficient representation
graph theory
proper interval graphs
unit interval graphs
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v35_nC_p247_Lin
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

Ejemplares similares

Ejemplares similares