IEICE TRANSACTIONS on Information
Partitioning a Multi-Weighted Graph to Connected Subgraphs of Almost Uniform Size
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E90-D No.2 pp.449-456
- Publication Date
- 2007/02/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1093/ietisy/e90-d.2.449
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science)
- Category
- Graph Algorithms
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Takehiro ITO, Kazuya GOTO, Xiao ZHOU, Takao NISHIZEKI, "Partitioning a Multi-Weighted Graph to Connected Subgraphs of Almost Uniform Size" in IEICE TRANSACTIONS on Information,
vol. E90-D, no. 2, pp. 449-456, February 2007, doi: 10.1093/ietisy/e90-d.2.449.
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.
URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e90-d.2.449/_p
Copy
@ARTICLE{e90-d_2_449,
author={Takehiro ITO, Kazuya GOTO, Xiao ZHOU, Takao NISHIZEKI, },
journal={IEICE TRANSACTIONS on Information},
title={Partitioning a Multi-Weighted Graph to Connected Subgraphs of Almost Uniform Size},
year={2007},
volume={E90-D},
number={2},
pages={449-456},
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.},
keywords={},
doi={10.1093/ietisy/e90-d.2.449},
ISSN={1745-1361},
month={February},}
Copy
TY - JOUR
TI - Partitioning a Multi-Weighted Graph to Connected Subgraphs of Almost Uniform Size
T2 - IEICE TRANSACTIONS on Information
SP - 449
EP - 456
AU - Takehiro ITO
AU - Kazuya GOTO
AU - Xiao ZHOU
AU - Takao NISHIZEKI
PY - 2007
DO - 10.1093/ietisy/e90-d.2.449
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E90-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2007
AB - 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.
ER -
English
