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...
| Autores principales: | Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L. |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_15710653_v35_nC_p247_Lin |
| Aporte de: |
Ejemplares similares
-
Short Models for Unit Interval Graphs
por: Lin, Min Chih, et al.
Publicado: (2009) -
On unit interval graphs with integer endpoints
por: Durán, G., et al. -
On unit interval graphs with integer endpoints
por: Durán, Guillermo A., et al.
Publicado: (2015) -
A faster algorithm for the cluster editing problem on proper interval graphs
por: Lin, M.C., et al. -
Recognition and characterization of unit interval graphs with integer endpoints
por: Durán, G., et al.