Reducing the Optimality Gap of Strictly Fundamental Cycle Bases in Planar Grids

Simple item page
dc.contributor.authorKöhler, Ekkehard
dc.contributor.authorLiebchen, Christian
dc.contributor.authorRizzi, Romeo
dc.contributor.authorWünsch, Gregor
dc.date.accessioned2021-12-17T10:07:07Z
dc.date.available2021-12-17T10:07:07Z
dc.date.issued2006
dc.description.abstractThe Minimum Cycle Basis~(MCB) Problem is a classical problem in combinatorial optimization. This problem can be solved in O(m2n+mn2log(n)). Much faster heuristics have been examined in the context of several practical applications. These heuristics restrain the solution space to strictly fundamental cycle bases, hereby facing a significant loss in quality. We complement these experimental studies by explaining theoretically why strictly fundamental cycle bases~(SFCB) in general must be much worse than general MCB.en
dc.identifier.issn2197-8085
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/15599
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-14372
dc.language.isoenen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.ddc510 Mathematiken
dc.subject.othercombinatorial optimizationen
dc.subject.othercycle basesen
dc.subject.otherstrictly fundamental cycle basesen
dc.subject.otherapproximationen
dc.subject.otheraverage stretchen
dc.titleReducing the Optimality Gap of Strictly Fundamental Cycle Bases in Planar Gridsen
dc.typeResearch Paperen
dc.type.versionsubmittedVersionen
tub.accessrights.dnbfreeen
tub.affiliationFak. 2 Mathematik und Naturwissenschaften::Inst. Mathematikde
tub.affiliation.facultyFak. 2 Mathematik und Naturwissenschaftende
tub.affiliation.instituteInst. Mathematikde
tub.publisher.universityorinstitutionTechnische Universität Berlinen
tub.series.issuenumber2006, 07en
tub.series.namePreprint-Reihe des Instituts für Mathematik, Technische Universität Berlinen
tub.subject.msc200090C27 Combinatorial optimizationen
tub.subject.msc200068R05 Combinatoricsen
tub.subject.msc200005C05 Treesen
tub.subject.msc200005C38 Paths and cyclesen

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Report-007-2006.pdf
Size:
253.37 KB
Format:
Adobe Portable Document Format
Download

Collections

Publications