An O(n(4)) Time Algorithm to Compute the Bisection Width of Solid Grid Graphs

作者：Feldmann Andreas Emil^*; Widmayer Peter

来源：Algorithmica, 2015, 71(1): 181-200.

DOI：10.1007/s00453-014-9928-y

• Bisection
• Solid grid graphs
• Planar graphs

The bisection problem asks for a partition of the vertices of a graph into two sets of size at most , so that the number of edges connecting the sets is minimised. A grid graph is a finite connected subgraph of the infinite two-dimensional grid. It is called solid if it has no holes. Papadimitriou and Sideri (Theory Comput Syst 29:97-110, 1996) gave an time algorithm to solve the bisection problem on solid grid graphs. We propose a novel approach that exploits structural properties of optimal cuts within a dynamic program. We show that our new technique leads to an time algorithm.

• 出版日期2015-1