Show simple item record

dc.contributor.author
Feldmann, Andreas Emil
dc.contributor.author
Das, Shantanu
dc.contributor.author
Widmayer, Peter
dc.date.accessioned
2017-10-13T11:51:40Z
dc.date.available
2017-06-10T21:21:32Z
dc.date.available
2017-10-13T11:51:40Z
dc.date.issued
2012-06
dc.identifier.uri
http://hdl.handle.net/20.500.11850/71724
dc.identifier.doi
10.3929/ethz-a-009937811
dc.description.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.
en_US
dc.language.iso
en
en_US
dc.publisher
ETH, Swiss Federal Institute of Technology Zurich, Institute of Theoretical Computer Science
en_US
dc.rights.uri
http://rightsstatements.org/page/InC-NC/1.0/
dc.subject
Bisection
en_US
dc.subject
GRAPHENZERLEGUNG (GRAPHENTHEORIE)
en_US
dc.subject
Corner cuts
en_US
dc.subject
M-cut
en_US
dc.subject
GRAPH PARTITIONING (GRAPH THEORY)
en_US
dc.subject
PROGRAMS AND ALGORITHMS FOR THE SOLUTION OF SPECIAL PROBLEMS
en_US
dc.subject
Grid graphs
en_US
dc.subject
Min-cut
en_US
dc.subject
PROGRAMME UND ALGORITHMEN ZUR LÖSUNG SPEZIELLER PROBLEME
en_US
dc.subject
Polygons
en_US
dc.title
Corner Cuts are Close to Optimal
en_US
dc.type
Report
dc.rights.license
In Copyright - Non-Commercial Use Permitted
dc.date.published
2013
ethz.title.subtitle
From Solid Grids to Polygons and Back
en_US
ethz.journal.title
Technical report / Swiss Federal Institute of Technology Zurich, Department of Computer Science
ethz.journal.volume
731
en_US
ethz.journal.issue
b
en_US
ethz.size
59 p.
en_US
ethz.version.edition
[Neue Version]
en_US
ethz.code.ddc
0 - Computer science, information & general works::004 - Data processing, computer science
en_US
ethz.notes
Technical reports D-Infk. See also http://e-citations.ethbib.ethz.ch/view/pub:104763.
en_US
ethz.identifier.nebis
009937811
ethz.publication.place
Zürich
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science
en_US
ethz.date.deposited
2017-06-10T21:24:32Z
ethz.source
ECOL
ethz.source
ECIT
ethz.identifier.importid
imp59366b445b50311143
ethz.identifier.importid
imp593650fd95b0228574
ethz.ecolpid
eth:7305
ethz.ecitpid
pub:113626
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2017-07-26T15:48:30Z
ethz.rosetta.lastUpdated
2017-10-13T11:51:44Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Corner%20Cuts%20are%20Close%20to%20Optimal&rft.jtitle=Technical%20report%20/%20Swiss%20Federal%20Institute%20of%20Technology%20Zurich,%20Department%20of%20Computer%20Science&rft.date=2012-06&rft.volume=731&rft.issue=b&rft.au=Feldmann,%20Andreas%20Emil&Das,%20Shantanu&Widmayer,%20Peter&rft.genre=report&
 Search via SFX

Files in this item

Thumbnail

Publication type

Show simple item record