Efficient algorithms for the inverse spanning tree problem
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 here
algorithms 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 ^2n) 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,
Ahuja and Orlin devised an algorithm with run time
O(n^2m\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's 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.
Download Information
Click on the following title to view and download the paper in PostScript format.
No download available, as per copyrights contract.
hochbaum@ieor.berkeley.edu
10/30/02