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
id paper:paper_15710653_v35_nC_p247_Lin
record_format dspace
spelling paper:paper_15710653_v35_nC_p247_Lin2023-06-08T16:24:25Z Short Models for Unit Interval Graphs Lin, Min Chih Soulignac, Francisco Juan algorithms and data structures efficient representation graph theory proper interval graphs 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 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. Fil:Lin, M.C. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Soulignac, F.J. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2009 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
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic algorithms and data structures
efficient representation
graph theory
proper interval graphs
unit interval graphs
spellingShingle algorithms and data structures
efficient representation
graph theory
proper interval graphs
unit interval graphs
Lin, Min Chih
Soulignac, Francisco Juan
Short Models for Unit Interval Graphs
topic_facet algorithms and data structures
efficient representation
graph theory
proper interval graphs
unit interval graphs
description 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.
author Lin, Min Chih
Soulignac, Francisco Juan
author_facet Lin, Min Chih
Soulignac, Francisco Juan
author_sort Lin, Min Chih
title Short Models for Unit Interval Graphs
title_short Short Models for Unit Interval Graphs
title_full Short Models for Unit Interval Graphs
title_fullStr Short Models for Unit Interval Graphs
title_full_unstemmed Short Models for Unit Interval Graphs
title_sort short models for unit interval graphs
publishDate 2009
url 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
work_keys_str_mv AT linminchih shortmodelsforunitintervalgraphs
AT soulignacfranciscojuan shortmodelsforunitintervalgraphs
_version_ 1768543294721097728

Ejemplares similares