A shifting algorithm for constrained min-max partition on trees

Eliezer Agasi, Ronald I. Becker, Yehoshua Perl

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

Let T = (V,E) be a rooted tree with n edges. We associate nonnegative weight w(v) and size s(v) with each vertex v in V. A q-partition of T into q connected components T1,T2,...,Tq is obtained by deleting k = q-1 edges of T, 1 ≤ k < n. The weight W(Ti) (or size S(Ti)) of component Ti is then the sum o weights (sizes) of the vertices of Ti. The height h(T) is the maximum number of edges of paths having one end at the root. If P is a partition with components T1...,Tq let WP = max1 ≤ i ≤ q W(Ti). The following two problems are considered: 1. Size-constrained min-max problem: Find a q-partition of T for which WP is a minimum over all partitions P satisfying S(Ti) ≤ M (M > 0). 2. Height-constrained min-max problem: Find a q-partition of T for which WP is a minimum over all partitions P satisfying height h(Ti) ≤ H (H is a positive integer). The first problem is shown to be NP-complete, while a polynomial algorithm is presented for the second problem.

Original languageEnglish (US)
Pages (from-to)1-28
Number of pages28
JournalDiscrete Applied Mathematics
Volume45
Issue number1
DOIs
StatePublished - Aug 2 1993

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'A shifting algorithm for constrained min-max partition on trees'. Together they form a unique fingerprint.

Cite this