A linear programming approach to increasing the weight of all minimum spanning trees

Mourad Baïou () and Fancisco Barahona
Additional contact information
Mourad Baïou: CECO - Laboratoire d'économétrie de l'École polytechnique - X - École polytechnique - IP Paris - Institut Polytechnique de Paris - CNRS - Centre National de la Recherche Scientifique
Fancisco Barahona: CECO - Laboratoire d'économétrie de l'École polytechnique - X - École polytechnique - IP Paris - Institut Polytechnique de Paris - CNRS - Centre National de la Recherche Scientifique

Working Papers from HAL

Abstract: Given a graph where increasing the weight of an edge has a nondecreasing convex piecewise linear cost, we study the problem of finding a minimum cost increase of the weights so that the value of all minimum spanning trees is equal to some target value. We formulate this as a combinatorial linear program and give an algorithm.

Date: 2005
Note: View the original document on HAL open archive server: https://hal.science/hal-00242975
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://hal.science/hal-00242975/document (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:wpaper:hal-00242975

Access Statistics for this paper

More papers in Working Papers from HAL
Bibliographic data for series maintained by CCSD ().