Mostrar el registro sencillo del ítem
dc.contributor.author
Soulignac, Francisco Juan
dc.date.available
2018-04-04T17:29:01Z
dc.date.issued
2017-04
dc.identifier.citation
Soulignac, Francisco Juan; Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter I: theory; Brown University; Journal of Graph Algorithms and Applications; 21; 4; 4-2017; 455-489
dc.identifier.issn
1526-1719
dc.identifier.uri
http://hdl.handle.net/11336/40726
dc.description.abstract
This is the first of two chapters of a work in which we consider the unrestricted, minimal, and bounded representation problems for unit interval (UIG) and unit circular-arc (UCA) graphs. In the unrestricted version, a proper circular-arc (PCA) model M is given and the goal is to obtain an equivalent UCA model U . In the bounded version, M is given together with some lower and upper bounds that the beginning points of U must satisfy. In the minimal version, we have to find a minimal model equivalent to M , in which the circumference of the circle and length of the arcs must be simultaneously as small as possible. In this chapter we motivate these problems from an historical perspective, and we develop the theoretical framework required for the algorithms in Chapter II. We present new characterizations of those PCA models that have equivalent UCA models, and of those UCA models with a circle of circumference c and the arcs of length ℓ . We also prove that every UCA model is equivalent to a minimal one. We remark that all our results are of an algorithmic nature and can be readily employed to solve the problems at hand, even though these algorithms are not as efficient as those in Chapter II.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
Brown University
dc.rights
info:eu-repo/semantics/openAccess
dc.rights.uri
https://creativecommons.org/licenses/by/2.5/ar/
dc.subject.classification
Ciencias de la Computación
dc.subject.classification
Ciencias de la Computación e Información
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
dc.subject.classification
Matemática Pura
dc.subject.classification
Matemáticas
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
dc.title
Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter I: theory
dc.type
info:eu-repo/semantics/article
dc.type
info:ar-repo/semantics/artículo
dc.type
info:eu-repo/semantics/publishedVersion
dc.date.updated
2018-04-04T14:13:49Z
dc.journal.volume
21
dc.journal.number
4
dc.journal.pagination
455-489
dc.journal.pais
Estados Unidos
dc.description.fil
Fil: Soulignac, Francisco Juan. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de Quilmes. Departamento de Ciencia y Tecnología; Argentina
dc.journal.title
Journal of Graph Algorithms and Applications
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/http://jgaa.info/getPaper?id=425
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.7155/jgaa.00425
Archivos asociados