首页 | 本学科首页   官方微博 | 高级检索  
     


A linear time algorithm for balance vertices on trees
Affiliation:1. Le Quy Don Technical University, Viet Nam;2. Hanoi Department of Science and Technology, Viet Nam;3. Queen''s University, Belfast, UK;4. Duy Tan University, Viet Nam;1. Department of Information Engineering and Computer Science, Feng Chia University, Taichung, 40724, Taiwan, ROC;2. Department of Computer Science and Information Engineering, Asia University, Taichung, 41354, Taiwan, ROC;3. Department of Computer Science, National Tsing Hua University, 30013 No. 101, Section 2, Kuang-Fu Road, Hsinchu, 30013, Taiwan, ROC;4. College of Information Technology, The University of Danang, Danang University Village, Luu Quang Vu Street, Danang, Vietnam;1. University of Illinois Urbana-Champaign, Department of Industrial and Enterprise Systems Engineering, United States;2. RWTH Aachen University, School of Business and Economics, Germany;3. University of Waterloo, Department of Combinatorics & Optimization, Canada
Abstract:The concept of balance vertices was first investigated by Reid (1999). For the main result “the balance vertices of a tree consist of a single vertex or two adjacent vertices”, Shan and Kang (2004) and Reid and DePalma (2005) improved the length and technique of the proof. In this paper we further discuss the balance vertices on trees in a generalization context. We do not only provide a simple efficient proof for the relevant result but also develop a linear time algorithm to find the set of balance vertices on the underlying tree.
Keywords:Balance vertices  Tree  Complexity
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号