Thinness of product graphs

dc.creatorBonomo, Flavia
dc.creatorGonzález, Carolina Lucía
dc.creatorde Souza Oliveira, Fabiano
dc.creatorSampaio Jr., Moysés S.
dc.creatorSzwarcfiter, Jayme L.
dc.date2022-05
dc.date.accessioned2023-08-30T23:43:54Z
dc.date.available2023-08-30T23:43:54Z
dc.identifierhttp://hdl.handle.net/11336/204618
dc.identifierBonomo, 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.identifier0166-218X
dc.identifierCONICET Digital
dc.identifierCONICET
dc.identifier.urihttps://repositorioslatinoamericanos.uchile.cl/handle/2250/8542730
dc.descriptionThe 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.descriptionFil: 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.descriptionFil: 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.descriptionFil: de Souza Oliveira, Fabiano. Universidade do Estado de Rio do Janeiro; Brasil
dc.descriptionFil: Sampaio Jr., Moysés S.. Universidade Federal do Rio de Janeiro; Brasil
dc.descriptionFil: Szwarcfiter, Jayme L.. Universidade Federal do Rio de Janeiro; Brasil
dc.formatapplication/pdf
dc.formatapplication/pdf
dc.languageeng
dc.publisherElsevier Science
dc.relationinfo:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S0166218X21001463
dc.relationinfo:eu-repo/semantics/altIdentifier/doi/10.1016/j.dam.2021.04.003
dc.rightsinfo:eu-repo/semantics/restrictedAccess
dc.rightshttps://creativecommons.org/licenses/by-nc-nd/2.5/ar/
dc.subjectCOMPLETE THINNESS
dc.subjectGRAPH OPERATIONS
dc.subjectINDEPENDENT THINNESS
dc.subjectPRODUCT GRAPHS
dc.subjectPROPER THINNESS
dc.subjectTHINNESS
dc.subjecthttps://purl.org/becyt/ford/1.1
dc.subjecthttps://purl.org/becyt/ford/1
dc.subjecthttps://purl.org/becyt/ford/1.2
dc.subjecthttps://purl.org/becyt/ford/1
dc.titleThinness of product graphs
dc.typeinfo:eu-repo/semantics/article
dc.typeinfo:ar-repo/semantics/artículo
dc.typeinfo:eu-repo/semantics/publishedVersion


Este ítem pertenece a la siguiente institución