Zur Kurzanzeige

dc.contributor.author
Widmayer, Peter
dc.contributor.author
Feldmann, Andreas Emil
dc.contributor.author
Das, Shantanu
dc.date.accessioned
2017-07-21T10:21:00Z
dc.date.available
2017-06-10T17:58:02Z
dc.date.available
2017-07-21T10:17:41Z
dc.date.available
2017-07-21T10:21:00Z
dc.date.issued
2011
dc.identifier.uri
http://hdl.handle.net/20.500.11850/67937
dc.identifier.doi
10.3929/ethz-a-006906296
dc.description.abstract
The graph bisection problem asks to partition the n vertices of a graph into two sets of equal size so that the number of edges across the cut is minimum. We study nite, connected subgraphs of the innite twodimensional grid that do not have holes. Since bisection is an intricate problem, our interest is in the tradeo between runtime and solution quality that we get by limiting ourselves to a special type of cut, namely cuts with at most one bend each (corner cuts). We prove that optimum corner cuts get us arbitrarily close to equal sized parts, 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 eect of limiting these to corner cuts.
en_US
dc.format
application/pdf
dc.language.iso
en
en_US
dc.publisher
ETH, Department of Computer Science
en_US
dc.rights.uri
http://rightsstatements.org/page/InC-NC/1.0/
dc.title
Restricted cuts for bisections in solid grids
en_US
dc.type
Report
dc.rights.license
In Copyright - Non-Commercial Use Permitted
dc.date.published
2011
ethz.title.subtitle
A proof via polygons
en_US
ethz.journal.title
Technical report
ethz.journal.volume
731
en_US
ethz.size
43 p.
en_US
ethz.code.ddc
DDC - DDC::0 - Computer science, information & general works::004 - Data processing, computer science
en_US
ethz.notes
Technical Reports D-INFK.
en_US
ethz.identifier.nebis
006906296
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-10T17:59:30Z
ethz.source
ECOL
ethz.source
ECIT
ethz.identifier.importid
imp593650aee842546645
ethz.identifier.importid
imp59366b1ca8bf490521
ethz.ecolpid
eth:5155
ethz.ecitpid
pub:108018
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2017-07-13T07:33:23Z
ethz.rosetta.lastUpdated
2020-02-15T06:26:18Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Restricted%20cuts%20for%20bisections%20in%20solid%20grids&rft.jtitle=Technical%20report&rft.date=2011&rft.volume=731&rft.au=Widmayer,%20Peter&Feldmann,%20Andreas%20Emil&Das,%20Shantanu&rft.genre=report&
 Printexemplar via ETH-Bibliothek suchen

Dateien zu diesem Eintrag

Thumbnail

Publikationstyp

Zur Kurzanzeige