Vis enkel innførsel

dc.contributor.authorHalseth, Johan Torås
dc.date.accessioned2016-03-15T16:24:02Z
dc.date.available2016-03-15T16:24:02Z
dc.date.issued2016-02-15
dc.date.submitted2016-02-15eng
dc.identifier.urihttps://hdl.handle.net/1956/11669
dc.description.abstractIn this thesis we explore the technique of Region Decomposition for finding kernels for Planar Dominating Set. We redefine some concepts used in earlier work, fixing some ambiguities on the way. From those concepts we end up at the 335k kernel upper bound from Alber et. We then build on the results of Chen et al. to improve this upper bound to 55k. In the last part of the thesis we make use of a computer program to exhaustively search for reduced instances of regions, to be used together with the Region Decomposition technique. From the results from the computer program we are able to conclude that any region used in a Region Decomposition always can be reduced to an equivalent region having 12 vertices or less, in addition to its to endpoints. This let us arrive at a 43k kernel for Planar Dominating Set.en_US
dc.format.extent2830378 byteseng
dc.format.mimetypeapplication/pdfeng
dc.language.isoengeng
dc.publisherThe University of Bergenen_US
dc.subjectGrafalgoritmernb
dc.titleA 43k Kernel for Planar Dominating Set using Computer-Aided Reduction Rule Discoveryen_US
dc.typeMaster thesis
dc.rights.holderCopyright the Author. All rights reserveden_US
dc.description.degreeMaster i Informatikken_US
dc.description.localcodeMAMN-INF
dc.description.localcodeINF399
dc.subject.realfagstermerhttps://data.ub.uio.no/realfagstermer/c004774
dc.subject.nus754199eng
fs.subjectcodeINF399


Tilhørende fil(er)

Thumbnail

Denne innførselen finnes i følgende samling(er)

Vis enkel innførsel