Balanced tree partition problems with virtual nodes

Baoling Ning (), Jianzhong Li () and Shouxu Jiang ()
Additional contact information
Baoling Ning: Harbin Institute of Technology
Jianzhong Li: Harbin Institute of Technology
Shouxu Jiang: Harbin Institute of Technology

Journal of Combinatorial Optimization, 2019, vol. 37, issue 4, No 9, 1249-1265

Abstract: Abstract We study two variants of the Balanced Tree Partition (BTP for short) problem, whose goal is to find the minimum number of edges such that a partition of vertices into sets of equal size can be obtained after deleting those edges. We consider the BTP problem over trees with virtual nodes, which is motivated by the real applications in storing tree structured data distributively. Different from the traditional BTP problem, after deleting an edge from the tree, two virtual nodes must be added to provide the ability to recover the edge when computing, which will increase the size of some set in the partition and the set may become too large and need further splitting. Depending on whether or not to consider the partition set number k to be a parameter, to investigate the balanced tree partition methods over trees with virtual nodes, we formally defined two specific problems, $$k$$ k -VBTP and VBTP. The computational complexity and inapproximability of $$k$$ k -VBTP are analyzed, for the VBTP problem, a polynomial time algorithm is designed to find the optimal solution based on dynamic programming. Finally, the connections between $$k$$ k -VBTP and VBTP are built, and based the algorithm for VBTP, we design a heuristic algorithm for $$k$$ k -VBTP with performance guarantee.

Keywords: Balanced tree partition; Virtual node; Computational complexity; Approximation algorithms (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-018-0351-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:37:y:2019:i:4:d:10.1007_s10878-018-0351-1

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-018-0351-1

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().