Partitioning a graph of bounded tree-width to connected subgraphs of almost uniform size

Journal of Discrete Algorithms - Tập 4 - Trang 142-154 - 2006
Takehiro Ito1, Xiao Zhou1, Takao Nishizeki1
1Graduate School of Information Sciences, Tohoku University, Aoba-yama 6-6-05, Sendai, 980-8579, Japan

Tài liệu tham khảo

Arnborg, 1991, Easy problems for tree-decomposable graphs, J. Algorithms, 12, 308, 10.1016/0196-6774(91)90006-K Bodlaender, 1990, Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees, J. Algorithms, 11, 631, 10.1016/0196-6774(90)90013-5 Bozkaya, 2003, A tabu search heuristic and adaptive memory procedure for political districting, European J. Oper. Res., 144, 12, 10.1016/S0377-2217(01)00380-0 Garey, 1979 Gonzalez, 1977 Ito, 2004, Partitioning a weighted graph to connected subgraphs of almost uniform size, vol. 3353, 365 Kundu, 1977, A linear tree partitioning algorithm, SIAM J. Comput., 6, 151, 10.1137/0206012 Lucertini, 1993, Most uniform path partitioning and its use in image processing, Discrete Appl. Math., 42, 227, 10.1016/0166-218X(93)90048-S Perl, 1981, Max-min tree partitioning, J. ACM, 28, 5, 10.1145/322234.322236 Takamizawa, 1982, Linear-time computability of combinatorial problems on series-parallel graphs, J. ACM, 29, 623, 10.1145/322326.322328 Tsichritzis, 1974 Williams, 1995, Political redistricting: a review, Papers in Regional Science, 74, 13, 10.1111/j.1435-5597.1995.tb00626.x