Partition on trees with supply and demand: Kernelization and algorithms

详细信息    查看全文

• 作者：Mugang Lin^a ; ^b ; Qilong Feng^a ; ^{csufeng@csu.edu.cn} ; Jianer Chen^a ; ^c ; Wenjun Li^a ; ^d
• 关键词：Fixed-parameter tractability ; Network reconfiguration ; Kernelizaton ; Branching algorithm
• 刊名：Theoretical Computer Science
• 出版年：2017
• 出版时间：2 January 2017
• 年：2017
• 卷：657
• 期：part_PA
• 页码：11-19
• 全文大小：451 K
• 卷排序：657

文摘

Network reconfiguration is an important research topic in the planning and operation of power distribution networks. In this paper, we study the partition problem on trees with supply and demand from parameterized computation perspective. We analyze the relationship between supply nodes and demand nodes, and give four reduction rules, which result in a kernel of size O(k2)O(k2) for the problem. Based on branching technique, a parameterized algorithm of running time O⁎(2.828k)O⁎(2.828k) is presented.