Mostrar el registro sencillo del ítem
dc.contributor.author
Bonomo, Flavia

dc.contributor.author
de Estrada, Diego

dc.date.available
2020-12-28T15:24:05Z
dc.date.issued
2019-05
dc.identifier.citation
Bonomo, Flavia; de Estrada, Diego; On the thinness and proper thinness of a graph; Elsevier Science; Discrete Applied Mathematics; 261; 5-2019; 78-92
dc.identifier.issn
0166-218X
dc.identifier.uri
http://hdl.handle.net/11336/121210
dc.description.abstract
Graphs with bounded thinness were defined in 2007 as a generalization of interval graphs. In this paper we introduce the concept of proper thinness, such that graphs with bounded proper thinness generalize proper interval graphs. We study the complexity of problems related to the computation of these parameters, describe the behavior of the thinness and proper thinness under three graph operations, and relate thinness and proper thinness to other graph invariants in the literature. Finally, we describe a wide family of problems that can be solved in polynomial time for graphs with bounded thinness, generalizing for example list matrix partition problems with bounded size matrix, and enlarge this family of problems for graphs with bounded proper thinness, including domination problems.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
Elsevier Science

dc.rights
info:eu-repo/semantics/restrictedAccess
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/
dc.subject
INTERVAL GRAPHS
dc.subject
PROPER INTERVAL GRAPHS
dc.subject
PROPER THINNESS
dc.subject
THINNESS
dc.subject.classification
Matemática Aplicada

dc.subject.classification
Matemáticas

dc.subject.classification
CIENCIAS NATURALES Y EXACTAS

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.title
On the thinness and proper thinness of a graph
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
2020-11-30T14:18:11Z
dc.journal.volume
261
dc.journal.pagination
78-92
dc.journal.pais
Países Bajos

dc.journal.ciudad
Amsterdam
dc.description.fil
Fil: Bonomo, Flavia. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigación en Ciencias de la Computación; Argentina
dc.description.fil
Fil: de Estrada, Diego. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina
dc.journal.title
Discrete Applied Mathematics

dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.dam.2018.03.072
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/abs/pii/S0166218X1830180X
Archivos asociados