On star and biclique edge-colorings

Volver a la Vista simple
dc.conicet.fuenteindividual
dc.conicet.organizacionUniversidade Federal Fluminense
dc.conicet.organizacionUniversidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación
dc.conicet.organizacionConsejo Nacional de Investigaciones Científicas y Técnicas
dc.conicet.organizacionUniversidade Federal do Paraná
dc.conicet.organizacionInstituto Nacional de Metrologia, Qualidade e Tecnologia
dc.conicet.organizacionUniversity of Fribourg
dc.conicet.organizacionUniversidade Federal do Rio de Janeiro
dc.conicet.paisOrganizacionBrasil
dc.conicet.paisOrganizacionArgentina
dc.conicet.paisOrganizacionArgentina
dc.conicet.paisOrganizacionBrasil
dc.conicet.paisOrganizacionBrasil
dc.conicet.paisOrganizacionSuiza
dc.conicet.paisOrganizacionBrasil
dc.conicet.produccionid6354478
dc.contributor.authorDantas, Simone
dc.contributor.authorGroshaus, Marina Esther
dc.contributor.authorGuedes, André
dc.contributor.authorMachado, Raphael C. S.
dc.contributor.authorRies, Bernard
dc.contributor.authorSasaki, Diana
dc.date.accessioned2018-09-17T19:36:43Z
dc.date.available2018-09-17T19:36:43Z
dc.date.issued2017-01
dc.date.updated2018-09-14T13:16:28Z
dc.description.abstractA biclique of G is a maximal set of vertices that induces a complete bipartite subgraph Kp,q of G with at least one edge, and a star of a graph G is a maximal set of vertices that induces a complete bipartite graph K1,q. A biclique (resp. star) edge-coloring is a coloring of the edges of a graph with no monochromatic bicliques (resp. stars). We prove that the problem of determining whether a graph G has a biclique (resp. star) edge-coloring using two colors is NP-hard. Furthermore, we describe polynomial time algorithms for the problem in restricted classes: K3-free graphs, chordal bipartite graphs, powers of paths, and powers of cycles.es
dc.description.filFil: Dantas, Simone. Universidade Federal Fluminense; Brasil
dc.description.filFil: Groshaus, Marina Esther. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina
dc.description.filFil: Guedes, André. Universidade Federal do Paraná; Brasil
dc.description.filFil: Machado, Raphael C. S.. Instituto Nacional de Metrologia, Qualidade e Tecnologia ; Brasil
dc.description.filFil: Ries, Bernard. University of Fribourg; Suiza
dc.description.filFil: Sasaki, Diana. Universidade Federal do Rio de Janeiro; Brasil
dc.formatapplication/pdfes
dc.identifier.citationDantas, Simone; Groshaus, Marina Esther; Guedes, André; Machado, Raphael C. S.; Ries, Bernard; et al.; On star and biclique edge-colorings; Wiley; International Transactions in Operational Research; 24; 1-2; 1-2017; 339-346es
dc.identifier.institucionalCONICET
dc.identifier.issn0969-6016es
dc.identifier.repoCONICET Digital
dc.identifier.urihttp://hdl.handle.net/11336/59964
dc.journal.number1-2es
dc.journal.pagination339-346es
dc.journal.paisReino Unidoes
dc.journal.titleInternational Transactions in Operational Researches
dc.journal.volume24es
dc.language.isoenges
dc.publisherWileyes
dc.relation.alternativeidinfo:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1111/itor.12307
dc.relation.alternativeidinfo:eu-repo/semantics/altIdentifier/url/https://onlinelibrary.wiley.com/doi/full/10.1111/itor.12307
dc.rightsinfo:eu-repo/semantics/openAccess*
dc.rights.urihttps://creativecommons.org/licenses/by-nc-sa/2.5/ar/*
dc.subjectBiclique Edge-Coloringes
dc.subjectNp-Hardes
dc.subjectStar Edge-Coloringes
dc.subject.classificationCiencias de la Computaciónes
dc.subject.classificationCiencias de la Computación e Informaciónes
dc.subject.classificationCIENCIAS NATURALES Y EXACTASes
dc.titleOn star and biclique edge-coloringses
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.96dfc483-aed7-4b2d-94dc-06c59e6b1a74_A.pdf
Tamaño:
274.95 KB
Formato:
Adobe Portable Document Format
Descripción:
Descargar

Colecciones

Articulos(OCA CIUDAD UNIVERSITARIA)
Volver a la Vista simple