THE BISECTION WIDTH OF GRID GRAPHS

Authors
PAPADIMITRIOU CH SIDERI M
Citation
Ch. Papadimitriou et M. Sideri, THE BISECTION WIDTH OF GRID GRAPHS, Mathematical systems theory, 29(2), 1996, pp. 97-110
Citations number
8
Categorie Soggetti
System Science","Mathematics, Pure","Computer Science Theory & Methods",Mathematics
Journal title
Mathematical systems theory → ACNP
ISSN journal
00255661
Volume
29
Issue
2
Year of publication
1996
Pages
97 - 110
Database
ISI
SICI code
0025-5661(1996)29:2<97:TBWOGG>2.0.ZU;2-9
Abstract
A solid grid graph is a finite induced subgraph of the infinite grid t hat has no holes. We present a polynomial algorithm for computing the minimum number of edges we need to delete in order to divide a given s olid grid graph into two parts containing an equal number of nodes. Th e algorithm is based on dynamic programming, and it extends to several related problems, including grid graphs with a bounded number of hole s.