Name
Abstract | ||
|---|---|---|
Assume that each vertex of a graph G is assigned a nonnegative integer weight and that l and u are 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 an "almost uniform" 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 for paths in linear time and for trees in polynomial time. In this paper, we give polynomial-time algorithms to solve the three problems for trees, which are much simpler and faster than the known algorithms. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-92182-0_20 | ISAAC |
Keywords | Field | DocType |
weighted tree,number p,minimum partition problem,maximum partition problem,almost uniform size,series-parallel graph,polynomial time,nonnegative integer weight,graph g,minimum number,linear time,p-partition problem,connected component | Partition problem,Discrete mathematics,Combinatorics,Frequency partition of a graph,Connected component,Graph partition,Time complexity,Partition (number theory),Strongly connected component,Minimum k-cut,Mathematics | Conference |
Volume | ISSN | Citations |
5369 | 0302-9743 | 8 |
PageRank | References | Authors |
0.61 | 6 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Takehiro Ito | 1 | 260 | 40.71 |
| Takeaki Uno | 2 | 1319 | 107.99 |
| Xiao Zhou | 3 | 325 | 43.69 |
| Takao Nishizeki | 4 | 1771 | 267.08 |