Name
Abstract | ||
|---|---|---|
Assume that each vertex of a graph G is assigned a constant number q of nonnegative integer weights, and that q pairs of nonnegative integers li and ui, 1 ≤ i ≤ q, are given. One wishes to partition G into connected components by deleting edges from G so that the total i-th weights of all vertices in each component is at least li and at most ui for each index i, 1 ≤ i ≤ q. The problem of finding such a "uniform" partition is NP-hard for series-parallel graphs, and is strongly NP-hard for general graphs even for q = 1. In this paper we show that the problem and many variants can be solved in pseudo-polynomial time for series-parallel graphs and partial k-trees, that is, graphs with bounded tree-width. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1093/ietisy/e90-d.2.449 | COCOON |
Keywords | Field | DocType |
lower bound,algorithm,upper bound | Graph theory,Discrete mathematics,Indifference graph,Combinatorics,Modular decomposition,Vertex (graph theory),Clique-sum,Chordal graph,Pathwidth,1-planar graph,Mathematics | Journal |
Volume | Issue | ISSN |
E90-D | 2 | 0302-9743 |
ISBN | Citations | PageRank |
3-540-36925-2 | 3 | 0.48 |
References | Authors | |
9 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Takehiro Ito | 1 | 260 | 40.71 |
| Kazuya Goto | 2 | 3 | 0.48 |
| Xiao Zhou | 3 | 325 | 43.69 |
| Takao Nishizeki | 4 | 1771 | 267.08 |