[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

On the minimum routing cost clustered tree problem

  • Published:
Journal of Combinatorial Optimization Aims and scope Submit manuscript

Abstract

For an edge-weighted graph \(G=(V,E,w)\), in which the vertices are partitioned into k clusters \(\mathcal {R}=\{R_1,R_2,\ldots ,R_k\}\), a spanning tree T of G is a clustered spanning tree if T can be cut into k subtrees by removing \(k-1\) edges such that each subtree is a spanning tree for one cluster. In this paper, we show the inapproximability of finding a clustered spanning tree with minimum routing cost, where the routing cost is the total distance summed over all pairs of vertices. We present a 2-approximation for the case that the input is a complete weighted graph whose edge weights obey the triangle inequality. We also study a variant in which the objective function is the total distance summed over all pairs of vertices of different clusters. We show that the problem is polynomial-time solvable when the number of clusters k is 2 and NP-hard for \(k=3\). Finally, we propose a polynomial-time 2-approximation algorithm for the case of three clusters.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

References

  • Bao X, Liu Z (2012) An improved approximation algorithm for the clustered traveling salesman problem. Inf Process Lett 112(23):908–910

    Article  MathSciNet  MATH  Google Scholar 

  • Bilò D, Gualà L, Proietti G (2014) Finding best swap edges minimizing the routing cost of a spanning tree. Algorithmica 68(2):337–357

    Article  MathSciNet  MATH  Google Scholar 

  • Chen YH, Wu BY, Tang CY (2006) Approximation algorithms for some k-source shortest paths spanning tree problems. Networks 47(3):147–156

    Article  MathSciNet  MATH  Google Scholar 

  • Chisman JA (1975) The clustered traveling salesman problem. Comput Oper Res 2(2):115–119

    Article  Google Scholar 

  • Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) ntroduction to algorithms. MIT Press, San Francisco

    MATH  Google Scholar 

  • Dahlhaus E, Dankelmann P, Ravi R (2004) A linear-time algorithm to compute a MAD tree of an interval graph. Inf Process Lett 89(5):255–259

    Article  MathSciNet  MATH  Google Scholar 

  • Dijkstra EW (1959) A note on two problems in connexion with graphs. Numer Math 1(1):269–271

    Article  MathSciNet  MATH  Google Scholar 

  • Feremans C, Labbé M, Laporte G (2003) Generalized network design problems. Eur J Oper Res 148(1):1–13

    Article  MathSciNet  MATH  Google Scholar 

  • Fischetti M, Lancia G, Serafini P (2002) Exact algorithms for minimum routing cost trees. Networks 39(3):161–173

    Article  MathSciNet  MATH  Google Scholar 

  • Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. WH Freeman & Co, San Francisco

    MATH  Google Scholar 

  • Guttmann-beck N, Hassin R, Khuller S, Raghavachari B (2000) Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem. Algorithmica 28(4):422–437

    Article  MathSciNet  MATH  Google Scholar 

  • Hajiaghayi M, Khandekar R, Kortsarz G, Mestre J (2012) The checkpoint problem. Theor Comput Sci 452:88–99

    Article  MathSciNet  MATH  Google Scholar 

  • Hochuli A, Holzer S, Wattenhofer R (2014) Distributed approximation of minimum routing cost trees. In: Structural information and communication complexity. Lecture notes in computer science, vol 8576, pp 121–136

  • Ravelo S, Ferreira C (2015) A PTAS for the metric case of the minimum sum-requirement communication spanning tree problem. In: Algorithms and discrete applied mathematics, Lecture notes in computer science, vol 8959, Springer International Publishing, pp 9–20

  • Ravelo S, Ferreira C (2015) PTAS’s for some metric p-source communication spanning tree problems. In: WALCOM: algorithms and computation, Lecture notes in computer science, vol 8973, Springer International Publishing, pp 137–148

  • Singh A, Sundar S (2011) An artificial bee colony algorithm for the minimum routing cost spanning tree problem. Soft Comput 15(12):2489–2499

    Article  Google Scholar 

  • Tan QP, Due NN (2013) An experimental study of minimum routing cost spanning tree algorithms. In: 2013 international conference of soft computing and pattern recognition (SoCPaR), IEEE, pp 158–165

  • Wong R (1980) Worst-case analysis of network design problem heuristics. SIAM J Alg Discr Meth 1(1):51–63

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  • Wu BY (2006) On the intercluster distance of a tree metric. Theor Comput Sci 369(1):136–141

    Article  MathSciNet  MATH  Google Scholar 

  • Wu BY, Chao KM (2004) Spanning trees and optimization problem. Chapman & Hall, Boca Raton

    Book  MATH  Google Scholar 

  • Wu BY, Chao KM, Tang CY (2000) Approximation algorithms for the shortest total path length spanning tree problem. Discrete Appl Math 105:273–289

    Article  MathSciNet  MATH  Google Scholar 

  • Wu BY, Chao KM, Tang CY (2002) Light graphs with small routing cost. Networks 39(3):130–138

    Article  MathSciNet  MATH  Google Scholar 

  • Wu BY, Hsiao CY, Chao KM (2008) The swap edges of a multiple-sources routing tree. Algorithmica 50(3):299–311

    Article  MathSciNet  MATH  Google Scholar 

  • Wu BY, Lancia G, Bafna V, Chao KM, Ravi R, Tang CY (2000) A polynomial-time approximation scheme for minimum routing cost spanning trees. SIAM J Comput 29(3):761–778

    Article  MathSciNet  MATH  Google Scholar 

  • Wu BY, Lin CW (2015) On the clustered steiner tree problem. J Comb Optim 30(2):370–386

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

This work was supported in part by NSC 101-2221-E-194-025-MY3 and MOST 103-2221-E-194-025-MY3 from National Science Council/Ministry of Science and Technology, Taiwan, ROC

Author information

Authors and Affiliations

  1. National Chung Cheng University, ChiaYi, 621, Taiwan, ROC

    Chen-Wan Lin & Bang Ye Wu

Authors
  1. Chen-Wan Lin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Bang Ye Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Bang Ye Wu.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Lin, CW., Wu, B.Y. On the minimum routing cost clustered tree problem. J Comb Optim 33, 1106–1121 (2017). https://doi.org/10.1007/s10878-016-0026-8

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-016-0026-8

Keywords

Search

Navigation