Mostrar el registro sencillo del ítem

dc.contributor.author
Bonomo, Flavia  
dc.contributor.author
González, Carolina Lucía  
dc.contributor.author
de Souza Oliveira, Fabiano  
dc.contributor.author
Sampaio Jr., Moysés S.  
dc.contributor.author
Szwarcfiter, Jayme L.  
dc.date.available
2023-07-20T13:35:34Z  
dc.date.issued
2022-05  
dc.identifier.citation
Bonomo, Flavia; González, Carolina Lucía; de Souza Oliveira, Fabiano; Sampaio Jr., Moysés S.; Szwarcfiter, Jayme L.; Thinness of product graphs; Elsevier Science; Discrete Applied Mathematics; 312; 5-2022; 52-71  
dc.identifier.issn
0166-218X  
dc.identifier.uri
http://hdl.handle.net/11336/204618  
dc.description.abstract
The thinness of a graph is a width parameter that generalizes some properties of interval graphs, which are exactly the graphs of thinness one. Many NP-complete problems can be solved in polynomial time for graphs with bounded thinness, given a suitable representation of the graph. In this paper we study the thinness and its variations of graph products. We show that the thinness behaves “well” in general for products, in the sense that for most of the graph products defined in the literature, the thinness of the product of two graphs is bounded by a function (typically product or sum) of their thinness, or of the thinness of one of them and the size of the other. We also show for some cases the non-existence of such a function.  
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-nd/2.5/ar/  
dc.subject
COMPLETE THINNESS  
dc.subject
GRAPH OPERATIONS  
dc.subject
INDEPENDENT THINNESS  
dc.subject
PRODUCT 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
Thinness of product graphs  
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
2023-07-07T22:28:01Z  
dc.journal.volume
312  
dc.journal.pagination
52-71  
dc.journal.pais
Países Bajos  
dc.journal.ciudad
Amsterdam  
dc.description.fil
Fil: Bonomo, Flavia. 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. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigación en Ciencias de la Computación; Argentina  
dc.description.fil
Fil: González, Carolina Lucía. 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. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigación en Ciencias de la Computación; Argentina  
dc.description.fil
Fil: de Souza Oliveira, Fabiano. Universidade do Estado de Rio do Janeiro; Brasil  
dc.description.fil
Fil: Sampaio Jr., Moysés S.. Universidade Federal do Rio de Janeiro; Brasil  
dc.description.fil
Fil: Szwarcfiter, Jayme L.. Universidade Federal do Rio de Janeiro; Brasil  
dc.journal.title
Discrete Applied Mathematics  
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S0166218X21001463  
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.dam.2021.04.003  

Archivos asociados
Tamaño: 563.1Kb
Formato: PDF
.