Open access
Date
2012-06Type
- Report
ETH Bibliography
yes
Altmetrics
Abstract
We study the solution quality for min-cut problems on graphs when restricting the shapes of the allowed cuts. In particular we are interested in min-cut problems with additional size constraints on the parts being cut out from the graph. Such problems include the bisection problem, separator problem, or the sparsest cut problem. We therefore aim at cutting out a given number m of vertices from a graph using as few edges as possible. We consider this problem on solid grid graphs which are finite, connected subgraphs of the infinite two-dimensional grid that do not have holes. Our interest is in the tradeoff between the simplicity of the cut shapes and their solution quality: we study corner cuts in which each cut has at most one right-angled bend. We prove that optimum corner cuts get us arbitrarily close to a cut out part of size m, and that this limitation makes us lose only a constant factor in the quality of the solution. We obtain our result by a thorough study of cuts in polygons and the effect of limiting these to corner cuts. Show more
Permanent link
https://doi.org/10.3929/ethz-a-009937811Publication status
publishedJournal / series
Technical Report / ETH Zurich, Department of Computer ScienceVolume
Publisher
ETH, Swiss Federal Institute of Technology Zurich, Institute of Theoretical Computer ScienceEdition / version
[Neue Version]Subject
Bisection; GRAPHENZERLEGUNG (GRAPHENTHEORIE); Corner cuts; M-cut; GRAPH PARTITIONING (GRAPH THEORY); PROGRAMS AND ALGORITHMS FOR THE SOLUTION OF SPECIAL PROBLEMS; Grid graphs; Min-cut; PROGRAMME UND ALGORITHMEN ZUR LÖSUNG SPEZIELLER PROBLEME; PolygonsOrganisational unit
02150 - Dep. Informatik / Dep. of Computer Science
Notes
Technical reports D-Infk. See also http://e-citations.ethbib.ethz.ch/view/pub:104763.More
Show all metadata
ETH Bibliography
yes
Altmetrics