Skip to main content
SpringerLink
Log in

Minimum spanning trees in networks with varying edge weights

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

This paper considers the problem of determining minimum spanning trees in networks in which each edge weight can assume a finite number of distinct values. We use the algebraic structure of an underlying Hasse diagram to describe the relationship between different edge-weight realizations of the network, yielding new results on how MSTs change under multiple edge-weight perturbations. We investigate various implementation strategies for updating MSTs in this manner. Computational results are provided for some challenging test networks.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Ahuja, R., T. Magnanti, and J. Orlin. (1993). Network Flows: Theory, Algorithms, and Applications. Englewood Cliffs, NJ: Prentice Hall Publishing.

    Google Scholar 

  • Ahuja, R., T. Magnanti, J. Orlin, and M.R. Reddy. (1995). “Applications of Network Optimization.” In M. O. Ball, T. L. Magnanti, C. L. Monma, and G. L. Nemhauser (eds.), Handbooks in Operations Research and Management Science, Amsterdam: Elsevier Science B.V., vol. 7, pp. 1–83.

    Google Scholar 

  • Alexopoulos, C. (1997). “State Space Partitioning Methods for Stochastic Shortest Path Problems.” Networks, 30, 9–21.

    Article  Google Scholar 

  • Alexopoulos, C. and J. Jacobson. (2000). “State Space Partition Algorithms for Stochastic Systems with Applications to Minimum Spanning Trees.” Networks, 35, 118–138.

    Article  Google Scholar 

  • Bailey, M. P. (1994). “Solving a Class of Stochastic Minimization Problems.” Operations Research, 42, 428–438.

    Google Scholar 

  • Dixon, B., M. Rauch, and R. E. Tarjan. (1992). “Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time.” SIAM Journal on Computing, 6, 1184–1192.

    Article  Google Scholar 

  • Doulliez, P. and E. Jamoulle. (1972). “Transportation Networks with Random Arc Capacities.” R.A.I.R.O., 3, 45–60.

    Google Scholar 

  • Gabow, H. N. (1977). “Two Algorithms for Generating Weighted Spanning Trees in Order.” SIAM Journal on Computing, 6, 139–150.

    Article  Google Scholar 

  • Gabow, H. N., Z. Galil, T. Spencer, and R. E. Tarjan. (1986). “Efficient Algorithms for Finding Minimum Spanning Trees in Undirected and Directed Graphs.” Combinatorica, 2, 109–122.

    Article  Google Scholar 

  • Graham, R. L. and P. Hell. (1985). “On the History of the Minimum Spanning Tree Problem.” Ann. History of Comp., 7, 43–57.

    Google Scholar 

  • Gusfield, D. (1983). “A Note on Arc Tolerances in Sparse Shortest-Path and Network Flow Problems.” Networks, 13, 191–196.

    Article  Google Scholar 

  • Hutson, K. (2002). “Stochastic Minimum Spanning Trees.” Ph.D. Dissertation, Clemson University.

  • Jain, A. and J. W. Mamer. (1988). “Approximations for the Random Minimal Spanning Tree with Application to Network Provisioning.” Operations Research, 36, 575–584.

    Google Scholar 

  • Jarvis, J. and D. Shier. (1996). “An Improved Algorithm for Approximating the Performance of Stochastic Flow Networks.” INFORMS Journal on Computing, 8, 355–360.

    Article  Google Scholar 

  • Kulkarni, V. G. (1986). “Minimum Spanning Trees in Undirected Networks with Exponentially Distributed Arc Weights.” Networks, 16, 111–124.

    Article  Google Scholar 

  • Matsui, T. (1997). “A Flexible Algorithm for Generating All the Spanning Trees in Undirected Graphs.” Algorithmica, 18, 530–543.

    Google Scholar 

  • Shier, D. and C. Witzgall. (1980). “Arc Tolerances in Shortest Path and Network Flow Problems.” Networks, 10, 277–291.

    Article  Google Scholar 

  • Tarjan, R. (1982). “Sensitivity Analysis of Minimum Spanning Trees and Shortest Path Trees.” Inform. Process. Lett., 14, 30–33.

  • Tarjan, R. (1983). Data Structures and Network Algorithms. CBMS-NSF Regional Conference Series in Applied Mathematics 44. Philadelphia: SIAM Publishing.

  • Thulasiraman, K. (2004). “Graphs and Vector Spaces.” In J. L. Gross and J. Yellen (eds.), Handbook of Graph Theory. Boca Raton: CRC Press, pp. 533–556.

    Google Scholar 

  • Trotter, W. (1995). “Partially Ordered Sets.” In R. Graham, M. Grotschel, and L. Lovasz (eds.), Handbook of Combinatorics. Amsterdam: Elsevier Science B.V., pp. 433–480.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics   Computer Science, Denison University, Granville, Ohio, 43023, U.S.A

    Kevin R. Hutson

  2. Department of Mathematical Sciences, Clemson University, Clemson, South Carolina, 29634-0975, USA

    Douglas R. Shier

Authors
  1. Kevin R. Hutson
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Douglas R. Shier
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Douglas R. Shier.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Hutson, K.R., Shier, D.R. Minimum spanning trees in networks with varying edge weights. Ann Oper Res 146, 3–18 (2006). https://doi.org/10.1007/s10479-006-0043-6

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-006-0043-6

Keywords

Search

Navigation