Mostrar el registro sencillo del ítem
dc.contributor.author
Aguilera, Néstor Edgardo
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.contributor.author
Leoni, Valeria Alejandra
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.contributor.author
Nasini, Graciela Leonor
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.date.available
2019-09-24T17:02:52Z
dc.date.issued
2008-02
dc.identifier.citation
Aguilera, Néstor Edgardo; Leoni, Valeria Alejandra; Nasini, Graciela Leonor; Combinatorial Flexibility problems and their computational Complexity; Elsevier; Electronic Notes in Discrete Mathematics; 30; C; 2-2008; 303-308
dc.identifier.issn
1571-0653
dc.identifier.uri
http://hdl.handle.net/11336/84281
dc.description.abstract
The concept of flexibility-originated in the context of heat exchanger networks-is associated with a substructure which guarantees the performance of the original structure, in a given range of possible states. We extend this concept to combinatorial optimization problems, and prove several computational complexity results in this new framework. Under some monotonicity conditions, we prove that a combinatorial optimization problem polynomially transforms to its associated flexibility problem, but that the converse need not be true. In order to obtain polynomial flexibility problems, we have to restrict ourselves to combinatorial optimization problems on matroids. We also prove that, when relaxing in different ways the matroid structure, the flexibility problems become NP-complete. This fact is shown by proving the NP-completeness of the flexibility problems associated with the Shortest Path, Minimum Cut and Weighted Matching problems.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
Elsevier
![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.subject
COMBINATORIAL PROBLEMS
dc.subject
COMPUTATIONAL COMPLEXITY
dc.subject
FLEXIBILITY
dc.subject.classification
Otras 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
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
Combinatorial Flexibility problems and their computational Complexity
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
2019-09-20T14:16:49Z
dc.journal.volume
30
dc.journal.number
C
dc.journal.pagination
303-308
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: Aguilera, Néstor Edgardo. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Santa Fe. Instituto de Matemática Aplicada del Litoral. Universidad Nacional del Litoral. Instituto de Matemática Aplicada del Litoral; Argentina
dc.description.fil
Fil: Leoni, Valeria Alejandra. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario; Argentina. Universidad Nacional de Rosario; Argentina
dc.description.fil
Fil: Nasini, Graciela Leonor. Universidad Nacional de Rosario; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario; Argentina
dc.journal.title
Electronic Notes in Discrete Mathematics
![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/doi/http://dx.doi.org/10.1016/j.endm.2008.01.052
Archivos asociados