On the finding 2-(k,l)-core of a tree with arbitrary real weight

Document Type : Research Article

Authors

• S. M. Ashkezari
• J. Fathali

Shahrood University of Technology, University Blvd., Shahrood, Iran.

10.22067/ijnao.v9i1.65852

Abstract

Let T = (V, E) be a tree with | V |= n. A 2-(k, l)-core of T is two subtrees with at most k leaves and with a diameter of at most l, which the sum of the distances from all vertices to these subtrees is minimized. In this paper, we first investigate the problem of finding 2-(k, l)-core on an unweighted tree and show that there exists a solution that none of (k, l)-cores is a vertex. Also in the case that the sum of the weights of vertices is negative, we show that one of (k, l)-cores is a single vertex. Then an algorithm for finding the 2-(k, l)-core of a tree with the pos/neg weight is presented.

Keywords

• core
• Facility location
• Median subtree
• Semi-obnoxious

20.1001.1.24236977.2019.9.1.5.8

---

References

1. Becker R.I. Inductive algorithms on finite trees, Quaest Math., 13, (1990), 165–181.

2. Becker R.I., Lari I., Storchi G. and Scozzari A. Efficient algorithms for finding the (k, l)-core of tree networks, Networks, 40, (2002), 208–215.

3. Becker R.I. and Perl Y. Finding the two-core of a tree, Discrete Applied Mathematics, 11, (1985), 103–113.

4. Minieka E. and Patel N.H. On finding the core of a tree with a specified length, J. Alg., 4, (1983), 345–352.

5. Morgan C.A. and Slater P.J. A linear algorithm for a core of a tree, Journal of Algorithms, 1, (1980), 247–258.

6. Motevalli S. and Fathali J. A linear algorithm for finding core of weighted interval trees, Journal of Operational Research and Its Applications, 13, (2016), 101–111.

7. Motevalli S., Fathali J. and Zaferanieh M. An efficient algorithm for finding the semi-obnoxious (k,l)-core of a tree, Journal of Mathematical Modeling, 3, (2015), 129–144.

8. Peng S. and Lo W. Efficient algorithms for finding a core of a tree with a specified length, Journal of Algorithms 20, (1996), 445–458.

9. Peng S., Stephens A.B. and Yesha Y. Algorithms for a core and a k-tree core of a tree, J. Alg., 15, (1993), 143–159.

10. Rahbari M., Fthali J. and Mortazavi R. A hybrid algorithm for the path center problem, Global Analysis and Discrete Mathematics, 1, (2016), 83–92.

11. Shioura A. and Uno T. A linear time algorithm for finding a k-tree core, J. Alg., 23, (1997), 281–290.

12. Wang B.F. Finding a k-tree core and a k-tree center of a tree network in parallel, IEEE Transactions on Parallel and Distributed Systems, 9, (1998), 186–191.

13. Wang B.F. Finding a 2-core of a tree in linear time, SIAM Journal on Discrete Mathematics, 15, (2002), 193–210.

14. Wang Y., Wang D.Q., Liu W. and Tian B.Y. Efficient parallel algorithms for constructing a k-tree center and a k-tree core of a tree network, Lecture Notes in Computer Science 3827, Springer-Verlag Berlin Heidelberg, (2005), 553–562.

15. Wang Y. and Wang Y. Efficient algorithms for constructing a (k,l)-center and a (k,l)-core in a tree network, Fourth International Conference on Innovative Computing, Information and Control, (ICICIC), 2009.

16. Zaferanieh M. and Fathali J. Ant colony and simulated annealing algorithms for finding the core of a graph, World Applied Science Journal, 7, (2009), 1335–1341.

17. Zaferanieh M. and Fathali J. Finding a core of a tree with pos/neg weight, Math. Meth. Oper. Res., 76, (2012), 147–160.

18. Zelinka B. Medians and peripherians of trees, Archvum Mathematicum, 4, (1968), 87–95.

19. Zhou J., Kang L. and Shan E. Two paths location of a tree with positive or negative weights, Theoretical Computer Science, 607, (2015), 296–305.