Efficient Algorithms for the Inverse Spanning-Tree Problem

Dorit S. Hochbaum ()
Additional contact information
Dorit S. Hochbaum: Department of Industrial Engineering and Operations Research, Walter A. Haas School of Business, University of California, Berkeley, California 94720

Operations Research, 2003, vol. 51, issue 5, 785-797

Abstract: The inverse spanning-tree problem is to modify edge weights in a graph so that a given tree T is a minimum spanning tree. The objective is to minimize the cost of the deviation. The cost of deviation is typically a convex function. We propose algorithms here that are faster than all known algorithms for the problem. Our algorithm's run time for any convex inverse spanning-tree problem is O ( nm log 2 n ) for a graph on n nodes and m edges plus the time required to find the minima of the n convex deviation functions. This not only improves on the complexity of previously known algorithms for the general problem, but also for algorithms devised for special cases. For the case when the objective is weighted absolute deviation, Sokkalingam et al. (1999) devised an algorithm with run time O ( n 2 m log( nC )) for C the maximum edge weight. For the sum of absolute deviations our algorithm runs in time O ( n 2 log n ), matching the run time of a recent (Ahuja and Orlin 2000) improvement for this case. A new algorithm for bipartite matching in path graphs is reported here with complexity of O ( n 1.5 log n ). This leads to a second algorithm for the sum of absolute deviations running in O ( n 1.5 log n log C ) steps.

Keywords: Programming: integer; algorithms; optimization in integers; Network/graphs: flow algorithms; parametric minimum cut; Mathematics: convexity; convex optimization problem (search for similar items in EconPapers)
Date: 2003
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (22)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.51.5.785.16756 (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:inm:oropre:v:51:y:2003:i:5:p:785-797

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().