A 7/6-Approximation Algorithm for the Max-Min Connected Bipartition Problem on Grid Graphs

被引：0

作者：

Wu, Bang Ye ^{[1
]}

机构：

[1] Natl Chung Cheng Univ, Chiayi 621, Taiwan

来源：

COMPUTATIONAL GEOMETRY, GRAPHS AND APPLICATIONS | 2011年 / 7033卷

关键词：

algorithm; approximation algorithm; non-separating path; connected partition; grid graph; TREES;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

For a given graph with nonnegative weights on nodes, the max-min connected bipartition problem looks for a way to partition the graph into two connected subgraphs such that the minimum weight of the two subgraphs is maximized. In this paper, we give a polynomial time 7/6-approximation algorithm for grid graphs. The approximation ratio is currently the best result achieved in polynomial time.

引用

页码：188 / 194

页数：7

共 12 条

[1]

Becker R, 1998, NETWORKS, V32, P115, DOI 10.1002/(SICI)1097-0037(199809)32:2<115::AID-NET4>3.0.CO

[2]

2-E

[3] A polynomial-time algorithm for max-min partitioning of ladders [J].

Becker, R ;

Lari, I ;

Lucertini, M ;

Simeone, B .

THEORY OF COMPUTING SYSTEMS, 2001, 34 (04) :353-374

[4] Lowest common ancestors in trees and directed acyclic graphs [J].

Bender, MA ;

Farach-Colton, M ;

Pemmasani, G ;

Skiena, S ;

Sumazin, P .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2005, 57 (02) :75-94

[5]

Chataigner F, 2007, DISCRETE MATH THEOR, V9, P177

[6] Approximating the maximally balanced connected partition problem in graphs [J].

Chlebikova, J .

INFORMATION PROCESSING LETTERS, 1996, 60 (05) :225-230

[7]

Even S., 1976, Theoretical Computer Science, V2, P339, DOI 10.1016/0304-3975(76)90086-4

[8]

Fredman ML, 1987, J ACM, V34, P209

[9] HOMOLOGY THEORY FOR SPANNING TREES OF A GRAPH [J].

LOVASZ, L .

ACTA MATHEMATICA ACADEMIAE SCIENTIARUM HUNGARICAE, 1977, 30 (3-4) :241-251

[10] MAX-MIN TREE PARTITIONING [J].

PERL, Y ;

SCHACH, SR .

JOURNAL OF THE ACM, 1981, 28 (01) :5-15

← 1 2 →