Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651580 | Electronic Notes in Discrete Mathematics | 2016 | 8 Pages |
Abstract
We consider the tree partition problem to partition the node set of a tree into subsets where the induced subgraph by each subset is connected and the total weight of nodes in a subset cannot exceed the capacity of the subset. We identify exponentially many valid inequalities for an integer programming formulation of the problem and develop a linear time separation algorithm for the valid inequalities.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Sunil Chopra, Kangbok Lee, Minseok Ryu, Sangho Shim,