Skip to main content
SpringerLink
Log in

The Swap Edges of a Multiple-Sources Routing Tree

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

Let T be a spanning tree of a graph G and S⊂V(G) be a set of sources. The routing cost of T is the total distance from all sources to all vertices. For an edge e of T, the swap edge of e is the edge f minimizing the routing cost of the tree formed by replacing e with f. Given an undirected graph G and a spanning tree T of G, we investigate the problem of finding the swap edge for every tree edge. In this paper, we propose an O(mlog n+n 2)-time algorithm for the case of two sources and an O(mn)-time algorithm for the case of more than two sources, where m and n are the numbers of edges and vertices of G, respectively.

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

  1. Di Salvo, A., Proietti, G.: Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor. In: SIROCCO’04. Lecture Notes in Computer Science, vol. 3104, pp. 99–110 (2004)

  2. Dixon, B., Rauch, M., Tarjan, R.E.: Verification and sensitivity analysis of minimum spanning trees in linear time. SIAM J. Comput. 21(6), 1184–1192 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  3. Grötschel, M., Monma, C.L., Stoer, M.: Design of survivable networks. In: Handbook in OR and MS, vol. 7, pp. 617–672. Elsevier, Amsterdam (1995)

    Google Scholar 

  4. Italiano, G.F., Ramaswami, R.: Maintaining spanning trees of small diameter. Algorithmica 22(3), 275–304 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  5. Iwano, K., Katoh, N.: Efficient algorithms for finding the most vital edge of a minimum spanning tree. Inf. Process. Lett. 48(5), 211–213 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  6. Nardelli, E., Proietti, G., Widmayer, P.: A faster computation of the most vital edge of a shortest path. Inf. Process. Lett. 79(2), 81–85 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  7. Nardelli, E., Proietti, G., Widmayer, P.: Swapping a failing edge of a single source shortest paths tree is good and fast. Algorithmica 35(1), 56–74 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  8. Wu, B.Y.: A polynomial time approximation scheme for the two-source minimum routing cost spanning trees. J. Algorithms 44, 359–378 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  9. Wu, B.Y.: Approximation algorithms for the optimal p-source communication spanning tree. Discrete Appl. Math. 143, 31–42 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  10. Wu, B.Y., Chao, K.-M.: Spanning Trees and Optimization Problems. Chapman & Hall/CRC Press, New York (2004)

    MATH  Google Scholar 

  11. Wu, B.Y., Chao, K.-M., Tang, C.Y.: Approximation algorithms for some optimum communication spanning tree problems. Discrete Appl. Math. 102, 245–266 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  12. Wu, B.Y., Lancia, G., Bafna, V., Chao, K.-M., Ravi, R., Tang, C.Y.: A polynomial time approximation scheme for minimum routing cost spanning trees. SIAM J. Comput. 29, 761–778 (1999)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Information Engineering, Shu-Te University, YenChau, Kaohsiung, 824, Taiwan

    Bang Ye Wu

  2. Department of Computer Science and Information Engineering, National Taiwan University, Taipei, 106, Taiwan

    Chih-Yuan Hsiao

  3. Department of Computer Science and Information Engineering/Graduate Institute of Networking and Multimedia, National Taiwan University, Taipei, 106, Taiwan

    Kun-Mao Chao

Authors
  1. Bang Ye Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Chih-Yuan Hsiao
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Kun-Mao Chao
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Kun-Mao Chao.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Wu, B.Y., Hsiao, CY. & Chao, KM. The Swap Edges of a Multiple-Sources Routing Tree. Algorithmica 50, 299–311 (2008). https://doi.org/10.1007/s00453-007-9080-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-007-9080-z

Keywords

Search

Navigation