Name
Abstract | ||
|---|---|---|
Assume that each vertex of a graph G is assigned a nonnegative integer weight and that l and u are given integers such that 0≤l≤u. One wishes to partition G into connected components by deleting edges from G so that the total weight of each component is at least l and at most u. Such a partition is called an (l,u)-partition. We deal with three problems to find an (l,u)-partition of a given graph: the minimum partition problem is to find an (l,u)-partition with the minimum number of components; the maximum partition problem is defined analogously; and the p-partition problem is to find an (l,u)-partition with a given number p of components. All these problems are NP-hard even for series-parallel graphs, but are solvable in linear time for paths. In this paper, we present the first polynomial-time algorithm to solve the three problems for arbitrary trees. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/s00453-010-9485-y | Algorithmica |
Keywords | Field | DocType |
Algorithm,Dynamic programming,Fast Fourier transform,Graph partition,Polynomial-time,Subtree,Tree | Partition problem,Cut,Discrete mathematics,Combinatorics,Rank of a partition,Frequency partition of a graph,Partition (number theory),Graph partition,Strongly connected component,Partition refinement,Mathematics | Journal |
Volume | Issue | ISSN |
62 | 3-4 | 0178-4617 |
Citations | PageRank | References |
4 | 0.48 | 7 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Takehiro Ito | 1 | 260 | 40.71 |
| Takao Nishizeki | 2 | 1771 | 267.08 |
| Michael Schröder | 3 | 5 | 1.17 |
| Takeaki Uno | 4 | 1319 | 107.99 |
| Xiao Zhou | 5 | 325 | 43.69 |