Paper Info
Title
The bisection width of grid graphs
Abstract
A solid grid graph is a finite induced subgraph of the infinite grid that 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 solid grid graph into two parts containing an equal number of nodes. The algorithm is based on dynamic programming, and it extends to several related problems, including grid graphs with a bounded number of holes.
Year
DOI
Venue
1990
https://doi.org/10.1007/BF01305310
Mathematical systems theory
Keywords
Field
DocType
Planar Graph,Boundary Node,Hamilton Path,Boundary Edge,Dual Graph
Discrete mathematics,Combinatorics,Grid network,Computer science,Induced subgraph,Dual graph,Alpha-numeric grid,Treewidth,Lattice graph,Universal graph,Planar graph
Conference
Volume
Issue
ISSN
29
2
0025-5661
Citations 
PageRank 
References 
18
1.65
5
Authors
2
Name
Order
Citations
PageRank
Christos H. Papadimitriou1166713192.54
Martha Sideri240946.17