Name
Abstract | ||
|---|---|---|
Assume that each vertex of a graph G is assigned a nonnegative integer weight and that l and u are nonnegative integers. One wish 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) \mbox{-}$partition. We deal with three problems to find an $(l, u) \mbox{-}$partition of a given graph. The minimum partition problem is to find an $(l, u) \mbox{-}$partition with the minimum number of components. The maximum partition problem is defined similarly. The p-partition problem is to find an $(l, u) \mbox{-}$partition with a fixed number p of components. All these problems are NP-complete or NP-hard even for series-parallel graphs. In this paper we show that both the minimum partition problem and the maximum partition problem can be solved in time O(u4n) and the p-partition problem can be solved in time O(p2u4n) for any series-parallel graph of n vertices. The algorithms can be easily extended for partial k-trees, that is, graphs with bounded tree-width. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1007/978-3-540-30559-0_31 | WG |
Keywords | DocType | Volume |
weighted graph,uniform size,fixed number p,minimum partition problem,maximum partition problem,connected subgraphs,time o,nonnegative integer weight,graph g,series-parallel graph,minimum number,nonnegative integer,p-partition problem,connected component | Conference | 3353 |
ISSN | ISBN | Citations |
0302-9743 | 3-540-24132-9 | 2 |
PageRank | References | Authors |
0.47 | 7 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Takehiro Ito | 1 | 260 | 40.71 |
| Xiao Zhou | 2 | 325 | 43.69 |
| Takao Nishizeki | 3 | 1771 | 267.08 |