مساله پیدا کردن –(k, l) − ٢هسته روی درختهای با وزن حقیقی

Iranian Journal of Numerical Analysis and Optimization

Article 5, Volume 9, Issue 1 - Serial Number 15, January 0, Pages 93-104   

Document Type: Research Article

DOI: 10.22067/ijnao.v9i1.65852

Author

جعفر فتحعلی^*

دانشگاه صنعتی شاهرود، دانشکده علوم ریاضی

Abstract

فرض کنید (T = (V, Eدرختی شامل nراس باشد. یک –(k, l)− ٢هسته از درخت Tشامل دو زیر درخت مجزا از Tمی باشد که هر یک از آنها حداکثر دارای Tبرگ و حداکثر قطر lهستند، همچنین مجموع فاصله تمام رئوس درخت تا این دو زیردرخت کمینه است. در این مقاله در ابتدا به بررسی مساله پیدا کردن –(k, l) − ٢هسته روی درختی که در آن وزن تمام رئوس یکسان است می پردازیم و نشان می دهیم جوابی برای این مساله وجود دارد که هیچ یک از هسته ها یک راس تنها نیست. سپس الگوریتمی برای پیدا کردن –(k, l) − ٢هسته روی درختهایی که وزن رئوس آنها می تواند مثبت یا منفی باشد، ارائه می دهیم.

Keywords

هسته; نظریه مکانیابی; زیردرخت میانه; نیمه ناخوشایند

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.