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

Guardado en:

Detalles Bibliográficos
Autores principales:	Durán, G., Fernández Slezak, F., Grippo, L.N., Oliveira, F., Szwarcfiter, J.L.
Formato:	JOUR
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:	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	todo:paper_0166218X_v245_n_p168_Duran
record_format	dspace
spelling	todo:paper_0166218X_v245_n_p168_Duran2023-10-03T15:03:45Z Recognition and characterization of unit interval graphs with integer endpoints Durán, G. Fernández Slezak, F. Grippo, L.N. Oliveira, F. Szwarcfiter, J.L. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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, G. Fernández Slezak, F. Grippo, L.N. Oliveira, F. Szwarcfiter, J.L. 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.
format	JOUR
author	Durán, G. Fernández Slezak, F. Grippo, L.N. Oliveira, F. Szwarcfiter, J.L.
author_facet	Durán, G. Fernández Slezak, F. Grippo, L.N. Oliveira, F. Szwarcfiter, J.L.
author_sort	Durán, G.
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
url	http://hdl.handle.net/20.500.12110/paper_0166218X_v245_n_p168_Duran
work_keys_str_mv	AT durang recognitionandcharacterizationofunitintervalgraphswithintegerendpoints AT fernandezslezakf recognitionandcharacterizationofunitintervalgraphswithintegerendpoints AT grippoln recognitionandcharacterizationofunitintervalgraphswithintegerendpoints AT oliveiraf recognitionandcharacterizationofunitintervalgraphswithintegerendpoints AT szwarcfiterjl recognitionandcharacterizationofunitintervalgraphswithintegerendpoints
_version_	1782027477721284608

Recognition and characterization of unit interval graphs with integer endpoints

Ejemplares similares