Recognition and characterization of unit interval graphs with integer endpoints

Duran, Guillermo Alfredo et al · Elsevier Science · 2017

Supplementary material available

Quick overview. Review the resource’s basic details, then access the content using the main button. This page shows only the information needed to identify, cite, and open the work.

Author / responsible party

Duran, Guillermo Alfredo et al

Publisher

Elsevier Science

Year

2017

ISSN

0166-218X

ISSN

0166-218X

Language

English

Resource access

Open the content from the main option or choose another available source.

CONICET Digital CONICET Digital OAI-PMH

Entrar por CONICET Digital

Main access

Supplementary material available

El enlace apunta a material asociado, anexos, tablas, datos o página complementaria. No se marca como libro/texto completo.

Open material

Summary

Descripción general del contenido del recurso.

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. Fil: Duran, Guillermo Alfredo. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad de Chile; Chile. Universidad de Buenos Aires; Argentina Fil: Fernández Slezak, F.. Universidad de Buenos Aires; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina

How to cite

Elegí el formato que necesitás y copiá la referencia al portapapeles.

APA 7

Duran, G. A. E. A. (2017). Recognition and characterization of unit interval graphs with integer endpoints. http://hdl.handle.net/11336/50305

MLA

Duran, Guillermo Alfredo et al. "Recognition and characterization of unit interval graphs with integer endpoints." 2017. http://hdl.handle.net/11336/50305.

Chicago

Duran, Guillermo Alfredo et al. 2017. "Recognition and characterization of unit interval graphs with integer endpoints.". http://hdl.handle.net/11336/50305.

Harvard

Duran, G. A. E. A. 2017, Recognition and characterization of unit interval graphs with integer endpoints, Elsevier Science, available at: http://hdl.handle.net/11336/50305 [Accessed 8 Aug. 2026].

Share and print

Save the record, copy its permanent link, or print it as a PDF.

Export reference

You can export the record in common formats for use in a reference manager.

RIS BibTeX

Resource details

Bibliographic information to help confirm that this is the correct material.

Title: Recognition and characterization of unit interval graphs with integer endpoints

Author / contributors: Duran, Guillermo Alfredo et al

Publisher: Elsevier Science

Publication year: 2017

ISSN: 0166-218X

ISSN: 0166-218X

Language: English

Subjects

Explore related resources through these subjects.

Forbidden Induced Subgraphs; Proper Interval Graphs; Unit Interval Graphs; https://purl.org/becyt/ford/1.1; https://purl.org/becyt/ford/1