Recognition and characterization of unit interval graphs with integer endpoints

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

Descripción completa

Detalles Bibliográficos
Autores principales:	Durán, Guillermo A., Fernandez Slezak, Florencia, Grippo, Luciano Norberto
Publicado:	2017
Materias:	Forbidden induced subgraphs Proper interval graphs Unit interval graphs Combinatorial mathematics Mathematical techniques Induced subgraphs Quadratic time Quadratic time algorithms Recognition algorithm Unit intervals Graphic methods
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v245_n_p168_Duran http://hdl.handle.net/20.500.12110/paper_0166218X_v245_n_p168_Duran
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_0166218X_v245_n_p168_Duran
record_format	dspace
spelling	paper:paper_0166218X_v245_n_p168_Duran2023-06-08T15:15:36Z Recognition and characterization of unit interval graphs with integer endpoints Durán, Guillermo A. Fernandez Slezak, Florencia Grippo, Luciano Norberto Forbidden induced subgraphs Proper interval graphs Unit interval graphs Combinatorial mathematics Mathematical techniques Forbidden induced subgraphs Induced subgraphs Proper interval graphs Quadratic time Quadratic time algorithms Recognition algorithm Unit interval graphs Unit intervals Graphic methods We study those unit interval graphs having a model with intervals of integer endpoints and prescribed length. We present a structural result for this graph subclass which leads to a quadratic-time recognition algorithm, giving as positive certificate a model of minimum total length and as negative certificate a forbidden induced subgraph. We also present a quadratic-time algorithm to build, given a unit interval graph, a unit interval model with integer endpoints for which the interval length is as minimum as possible. © 2017 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. 2017 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v245_n_p168_Duran http://hdl.handle.net/20.500.12110/paper_0166218X_v245_n_p168_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 induced subgraphs Proper interval graphs Unit interval graphs Combinatorial mathematics Mathematical techniques Forbidden induced subgraphs Induced subgraphs Proper interval graphs Quadratic time Quadratic time algorithms Recognition algorithm Unit interval graphs Unit intervals Graphic methods
spellingShingle	Forbidden induced subgraphs Proper interval graphs Unit interval graphs Combinatorial mathematics Mathematical techniques Forbidden induced subgraphs Induced subgraphs Proper interval graphs Quadratic time Quadratic time algorithms Recognition algorithm Unit interval graphs Unit intervals Graphic methods Durán, Guillermo A. Fernandez Slezak, Florencia Grippo, Luciano Norberto Recognition and characterization of unit interval graphs with integer endpoints
topic_facet	Forbidden induced subgraphs Proper interval graphs Unit interval graphs Combinatorial mathematics Mathematical techniques Forbidden induced subgraphs Induced subgraphs Proper interval graphs Quadratic time Quadratic time algorithms Recognition algorithm Unit interval graphs Unit intervals Graphic methods
description	We study those unit interval graphs having a model with intervals of integer endpoints and prescribed length. We present a structural result for this graph subclass which leads to a quadratic-time recognition algorithm, giving as positive certificate a model of minimum total length and as negative certificate a forbidden induced subgraph. We also present a quadratic-time algorithm to build, given a unit interval graph, a unit interval model with integer endpoints for which the interval length is as minimum as possible. © 2017 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	Recognition and characterization of unit interval graphs with integer endpoints
title_short	Recognition and characterization of unit interval graphs with integer endpoints
title_full	Recognition and characterization of unit interval graphs with integer endpoints
title_fullStr	Recognition and characterization of unit interval graphs with integer endpoints
title_full_unstemmed	Recognition and characterization of unit interval graphs with integer endpoints
title_sort	recognition and characterization of unit interval graphs with integer endpoints
publishDate	2017
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v245_n_p168_Duran http://hdl.handle.net/20.500.12110/paper_0166218X_v245_n_p168_Duran
work_keys_str_mv	AT duranguillermoa recognitionandcharacterizationofunitintervalgraphswithintegerendpoints AT fernandezslezakflorencia recognitionandcharacterizationofunitintervalgraphswithintegerendpoints AT grippolucianonorberto recognitionandcharacterizationofunitintervalgraphswithintegerendpoints
_version_	1768543987828785152

Recognition and characterization of unit interval graphs with integer endpoints

Ejemplares similares