[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

The w-centroids and least w-central subtrees in weighted trees

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

Abstract

Let T be a weighted tree with a positive number w(v) associated with each vertex v. A subtree S is a w-central subtree of the weighted tree T if it has the minimum eccentricity \(e_L(S)\) in median graph \(G_{LW}\). A w-central subtree with the minimum vertex weight is called a least w-central subtree of the weighted tree T. In this paper we show that each least w-central subtree of a weighted tree either contains a vertex of the w-centroid or is adjacent to a vertex of the w-centroid. Also, we show that any two least w-central subtrees of a weighted tree either have a nonempty intersection or are adjacent.

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
$34.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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  • Bielak H, Pańczyk M (2012) A self-stabilizing algorithm for finding weighted centroid in trees. Ann UMCS Inform AI XII 2:27–37

    MathSciNet  MATH  Google Scholar 

  • Brandeau ML, Chiu SS (1989) An overview of representative problem in location research. Manage Sci 35:645–674

    Article  MathSciNet  Google Scholar 

  • Hakimi SL (1964) Optimal locations of switching centers and the absolute centers and medians of a graph. Oper Res 12:450–459

    Article  Google Scholar 

  • Hamina M, Peltola M (2011) Least central subtrees, center, and centroid of a tree. Networks 57:328–332

    Article  MathSciNet  Google Scholar 

  • Kariv O, Hakimi SL (1979) An algorithm approach to network location problems. II: the \(p\)-medians. SIAM J Appl Math 37:539–560

    Article  MathSciNet  Google Scholar 

  • Nieminen J, Peltola M (1999) The subtree center of a tree. Networks 34:272–278

    Article  MathSciNet  Google Scholar 

  • Ried KB (1991) Centroids to center in trees. Networks 21:11–17

    Article  MathSciNet  Google Scholar 

  • Smart C, Slater PJ (1999) Center, median, and centroid subgraphs. Networks 34:303–311

    Article  MathSciNet  Google Scholar 

  • Spoerhase J, Wirth H-C (2009) \((r, p)\)-centroid problems on paths and trees. Theoret Comput Sci 410:5128–5137

    Article  MathSciNet  Google Scholar 

  • Tamir A (1988) Improved complexity bounds for center location problems on networks by using dynamic data structures. SIAM J Discrete Math 1:377–396

    Article  MathSciNet  Google Scholar 

  • Tansel BC, Francis RL, Lowe TJ (1983) Location on networks: a survey-Part I: the \(p\)-center and \(p\)-median problems. Manage Sci 29:482–497

    Article  Google Scholar 

Download references

Acknowledgements

This work was partially supported by the National Nature Science Foundation of China (Grant Numbers: 11471210, 11571222). We are very thankful to the referees for their careful reading of this paper and all helpful comments.

Author information

Authors and Affiliations

  1. Department of Mathematics, Shanghai University, Shanghai, 200444, People’s Republic of China

    Erfang Shan & Liying Kang

  2. School of Management, Shanghai University, Shanghai, 200444, People’s Republic of China

    Erfang Shan

Authors
  1. Erfang Shan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Liying Kang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Erfang Shan or Liying Kang.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Shan, E., Kang, L. The w-centroids and least w-central subtrees in weighted trees. J Comb Optim 36, 1118–1127 (2018). https://doi.org/10.1007/s10878-017-0174-5

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-017-0174-5

Keywords

Mathematics Subject Classification