On the complexity of { k } -domination and k-tuple domination in graphs

Volver a la Vista simple
dc.conicet.fuenteunificacion
dc.conicet.organizacionUniversidad Nacional de Rosario
dc.conicet.organizacionUniversidad Nacional de Rosario
dc.conicet.organizacionConsejo Nacional de Investigaciones Científicas y Técnicas
dc.conicet.organizacionUniversidad Nacional de Rosario
dc.conicet.organizacionConsejo Nacional de Investigaciones Científicas y Técnicas
dc.conicet.paisOrganizacionArgentina
dc.conicet.paisOrganizacionArgentina
dc.conicet.paisOrganizacionArgentina
dc.conicet.paisOrganizacionArgentina
dc.conicet.paisOrganizacionArgentina
dc.conicet.produccionid6552226
dc.contributor.authorArgiroffo, Gabriela Rut
dc.contributor.authorLeoni, Valeria Alejandra
dc.contributor.authorTorres, Pablo Daniel
dc.date.accessioned2018-06-25T18:00:43Z
dc.date.available2018-06-25T18:00:43Z
dc.date.issued2015-06
dc.date.updated2018-06-25T12:39:19Z
dc.description.abstractWe consider two types of graph domination - {k}-domination and k-tuple domination, for a fixed positive integer k - and provide new NP-complete as well as polynomial time solvable instances for their related decision problems. Regarding NP-completeness results, we solve the complexity of the {k}-domination problem on split graphs, chordal bipartite graphs and planar graphs, left open in 2008. On the other hand, by exploiting Courcelle's results on Monadic Second Order Logic, we obtain that both problems are polynomial time solvable for graphs with clique-width bounded by a constant. In addition, we give an alternative proof for the linearity of these problems on strongly chordal graphs.es
dc.description.filFil: Argiroffo, Gabriela Rut. Universidad Nacional de Rosario; Argentina
dc.description.filFil: Leoni, Valeria Alejandra. Universidad Nacional de Rosario; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina
dc.description.filFil: Torres, Pablo Daniel. Universidad Nacional de Rosario; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina
dc.formatapplication/pdfes
dc.identifier.citationArgiroffo, Gabriela Rut; Leoni, Valeria Alejandra; Torres, Pablo Daniel; On the complexity of { k } -domination and k-tuple domination in graphs; Elsevier Science; Information Processing Letters; 115; 6-8; 6-2015; 556-561es
dc.identifier.institucionalCONICET
dc.identifier.issn0020-0190es
dc.identifier.repoCONICET Digital
dc.identifier.urihttp://hdl.handle.net/11336/49955
dc.journal.ciudadAmsterdames
dc.journal.number6-8es
dc.journal.pagination556-561es
dc.journal.paisPaíses Bajoses
dc.journal.titleInformation Processing Letterses
dc.journal.volume115es
dc.language.isoenges
dc.publisherElsevier Sciencees
dc.relation.alternativeidinfo:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.ipl.2015.01.007
dc.relation.alternativeidinfo:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S0020019015000162
dc.rightsinfo:eu-repo/semantics/openAccess*
dc.rights.urihttps://creativecommons.org/licenses/by-nc-nd/2.5/ar/*
dc.subjectChordal Graphses
dc.subjectComputational Complexityes
dc.subjectK-Tuple Dominationes
dc.subjectPlanar Graphses
dc.subjectSplit Graphses
dc.subject{ K } Dominationes
dc.subject.classificationMatemática Puraes
dc.subject.classificationMatemáticases
dc.subject.classificationCIENCIAS NATURALES Y EXACTASes
dc.titleOn the complexity of { k } -domination and k-tuple domination in graphses
dc.typeinfo:eu-repo/semantics/article
dc.typeinfo:ar-repo/semantics/artículo
dc.typeinfo:eu-repo/semantics/publishedVersion

Archivos

Bloque original

Miniatura
Nombre:
CONICET_Digital_Nro.5673bb46-3add-42b0-9517-d64ba45dfc55_D.pdf
Tamaño:
323.45 KB
Formato:
Adobe Portable Document Format
Descargar

Colecciones

Articulos(CCT - ROSARIO)
Volver a la Vista simple