Mostrar el registro sencillo del ítem
dc.contributor.author
Aguilera, Néstor Edgardo
dc.contributor.author
Leoni, Valeria Alejandra
dc.contributor.author
Nasini, Graciela Leonor
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
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
dc.subject.classification
Matemáticas
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
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
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
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.endm.2008.01.052
Archivos asociados