Mostrar el registro sencillo del ítem

dc.contributor.author
Dantas, Simone  
dc.contributor.author
Groshaus, Marina Esther  
dc.contributor.author
Guedes, André  
dc.contributor.author
Machado, Raphael C. S.  
dc.contributor.author
Ries, Bernard  
dc.contributor.author
Sasaki, Diana  
dc.date.available
2018-09-17T19:36:43Z  
dc.date.issued
2017-01  
dc.identifier.citation
Dantas, 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-346  
dc.identifier.issn
0969-6016  
dc.identifier.uri
http://hdl.handle.net/11336/59964  
dc.description.abstract
A 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.  
dc.format
application/pdf  
dc.language.iso
eng  
dc.publisher
Wiley  
dc.rights
info:eu-repo/semantics/openAccess  
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/  
dc.subject
Biclique Edge-Coloring  
dc.subject
Np-Hard  
dc.subject
Star Edge-Coloring  
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 star and biclique edge-colorings  
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
2018-09-14T13:16:28Z  
dc.journal.volume
24  
dc.journal.number
1-2  
dc.journal.pagination
339-346  
dc.journal.pais
Reino Unido  
dc.description.fil
Fil: Dantas, Simone. Universidade Federal Fluminense; Brasil  
dc.description.fil
Fil: 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.fil
Fil: Guedes, André. Universidade Federal do Paraná; Brasil  
dc.description.fil
Fil: Machado, Raphael C. S.. Instituto Nacional de Metrologia, Qualidade e Tecnologia ; Brasil  
dc.description.fil
Fil: Ries, Bernard. University of Fribourg; Suiza  
dc.description.fil
Fil: Sasaki, Diana. Universidade Federal do Rio de Janeiro; Brasil  
dc.journal.title
International Transactions in Operational Research  
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1111/itor.12307  
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://onlinelibrary.wiley.com/doi/full/10.1111/itor.12307  

Archivos asociados
Thumbnail
 
Tamaño: 274.9Kb
Formato: PDF
.