On unit interval graphs with integer endpoints

We study those unit interval graphs having a model with intervals of prescribed integer length. We present a structural result for this subclass which leads to a quadratic-time recognition algorithm of it, giving as positive certificate a model of minimum total length and as negative certificate a f...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Durán, Guillermo A., Fernandez Slezak, Florencia, Grippo, Luciano Norberto
Publicado: 2015
Materias:
Forbidden subgraphs
Proper interval graphs
Unit interval graphs
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v50_n_p445_Duran
http://hdl.handle.net/20.500.12110/paper_15710653_v50_n_p445_Duran
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_15710653_v50_n_p445_Duran
record_format dspace
spelling paper:paper_15710653_v50_n_p445_Duran2023-06-08T16:24:30Z On unit interval graphs with integer endpoints Durán, Guillermo A. Fernandez Slezak, Florencia Grippo, Luciano Norberto Forbidden subgraphs Proper interval graphs Unit interval graphs We study those unit interval graphs having a model with intervals of prescribed integer length. We present a structural result for this subclass which leads to a quadratic-time recognition algorithm of it, giving as positive certificate a model of minimum total length and as negative certificate a forbidden induced subgraph. © 2015 Elsevier B.V. Fil:Durán, G. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Fernández Slezak, F. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Grippo, L.N. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2015 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v50_n_p445_Duran http://hdl.handle.net/20.500.12110/paper_15710653_v50_n_p445_Duran
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Forbidden subgraphs
Proper interval graphs
Unit interval graphs
spellingShingle Forbidden subgraphs
Proper interval graphs
Unit interval graphs
Durán, Guillermo A.
Fernandez Slezak, Florencia
Grippo, Luciano Norberto
On unit interval graphs with integer endpoints
topic_facet Forbidden subgraphs
Proper interval graphs
Unit interval graphs
description We study those unit interval graphs having a model with intervals of prescribed integer length. We present a structural result for this subclass which leads to a quadratic-time recognition algorithm of it, giving as positive certificate a model of minimum total length and as negative certificate a forbidden induced subgraph. © 2015 Elsevier B.V.
author Durán, Guillermo A.
Fernandez Slezak, Florencia
Grippo, Luciano Norberto
author_facet Durán, Guillermo A.
Fernandez Slezak, Florencia
Grippo, Luciano Norberto
author_sort Durán, Guillermo A.
title On unit interval graphs with integer endpoints
title_short On unit interval graphs with integer endpoints
title_full On unit interval graphs with integer endpoints
title_fullStr On unit interval graphs with integer endpoints
title_full_unstemmed On unit interval graphs with integer endpoints
title_sort on unit interval graphs with integer endpoints
publishDate 2015
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v50_n_p445_Duran
http://hdl.handle.net/20.500.12110/paper_15710653_v50_n_p445_Duran
work_keys_str_mv AT duranguillermoa onunitintervalgraphswithintegerendpoints
AT fernandezslezakflorencia onunitintervalgraphswithintegerendpoints
AT grippolucianonorberto onunitintervalgraphswithintegerendpoints
_version_ 1768544521038069760

Ejemplares similares