Mostrar el registro sencillo del ítem
dc.contributor.author
Bonomo, Flavia
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.contributor.author
Cornaz, Deni
dc.contributor.author
Ekim, Tinaz
dc.contributor.author
Ries, Bernard
dc.date.available
2015-06-15T16:46:29Z
dc.date.issued
2013-11
dc.identifier.citation
Bonomo, Flavia; Cornaz, Deni; Ekim, Tinaz; Ries, Bernard; Perfectness of clustered graphs; Elsevier Science; Discrete Optimization; 10; 4; 11-2013; 296-303
dc.identifier.issn
1572-5286
dc.identifier.uri
http://hdl.handle.net/11336/737
dc.description.abstract
Given a clustered graph (G,V), that is, a graph G=(V,E) together with a partition V of its vertex set, the selective coloring problem consists in choosing one vertex per cluster such that the chromatic number of the subgraph induced by the chosen vertices is minimum. This problem can be formulated as a covering problem with a 0–1 matrix M(G,V). Nevertheless, we observe that, given (G,V), it is NP-hard to check if M(G,V) is conformal (resp. perfect). We will give a sufficient condition, checkable in polynomial time, for M(G,V) to be conformal that becomes also necessary if conformality is required to be hereditary. Finally, we show that M(G,V) is perfect for every partition V if and only if G belongs to a superclass of threshold graphs defined with a complex function instead of a real one.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
Elsevier Science
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.rights
info:eu-repo/semantics/openAccess
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/
dc.source
CiteSeerX
dc.subject
CONFORMAL MATRIX
dc.subject
PARTITION COLORING
dc.subject
PERFECT MATRIX
dc.subject
SELECTIVE COLORING
dc.subject
THRESHOLD GRAPH
dc.subject.classification
Ciencias de la Computación
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
Ciencias de la Computación e Información
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
Matemática Aplicada
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
Matemáticas
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.title
Perfectness of clustered 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
2016-03-30 10:35:44.97925-03
dc.journal.volume
10
dc.journal.number
4
dc.journal.pagination
296-303
dc.journal.pais
Países Bajos
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.journal.ciudad
Amsterdam
dc.description.fil
Fil: Bonomo, Flavia. Consejo Nacional de Invest.cientif.y Tecnicas. Oficina de Coordinacion Administrativa Ciudad Universitaria. Instituto de Investigaciones Matematicas; Argentina
dc.description.fil
Fil: Cornaz, Deni. Université Paris-Dauphine; Francia
dc.description.fil
Fil: Ekim, Tinaz. Boğaziçi University; Turquía
dc.description.fil
Fil: Ries, Bernard. Université Paris-Dauphine; Francia
dc.journal.title
Discrete Optimization
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S1572528613000443
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.disopt.2013.07.006
Archivos asociados