### 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.

Original language | English (US) |
---|---|

Pages (from-to) | 109-116 |

Number of pages | 8 |

Journal | Electronic Notes in Discrete Mathematics |

Volume | 52 |

DOIs | |

State | Published - Jun 1 2016 |

### Keywords

- Integer programming
- Separation algorithm
- Tree partitioning
- Valid inequality

### ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics

## Fingerprint Dive into the research topics of 'Separation Algorithm for Tree Partitioning Inequalities'. Together they form a unique fingerprint.

## Cite this

Chopra, S., Lee, K., Ryu, M., & Shim, S. (2016). Separation Algorithm for Tree Partitioning Inequalities.

*Electronic Notes in Discrete Mathematics*,*52*, 109-116. https://doi.org/10.1016/j.endm.2016.03.015