Partitioning a Multi-Weighted Graph to Connected Subgraphs of Almost Uniform Size(Graph Algorithms,<Special Section>Foundations of Computer Science)

概要

論文の詳細を見る
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 l_i and u_i, 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 l_i and at most u_i 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.
社団法人電子情報通信学会の論文
2007-02-01