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
id todo:paper_15710653_v35_nC_p247_Lin
record_format dspace
spelling todo:paper_15710653_v35_nC_p247_Lin2023-10-03T16:27:04Z Short Models for Unit Interval Graphs Lin, M.C. Soulignac, F.J. Szwarcfiter, J.L. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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, M.C.
Soulignac, F.J.
Szwarcfiter, J.L.
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.
format JOUR
author Lin, M.C.
Soulignac, F.J.
Szwarcfiter, J.L.
author_facet Lin, M.C.
Soulignac, F.J.
Szwarcfiter, J.L.
author_sort Lin, M.C.
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
url http://hdl.handle.net/20.500.12110/paper_15710653_v35_nC_p247_Lin
work_keys_str_mv AT linmc shortmodelsforunitintervalgraphs
AT soulignacfj shortmodelsforunitintervalgraphs
AT szwarcfiterjl shortmodelsforunitintervalgraphs
_version_ 1807323254763814912

Ejemplares similares