Show simple item record

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.urihttp://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.eng
dc.format.extent2830378 byteseng
dc.format.mimetypeapplication/pdfeng
dc.language.isoengeng
dc.publisherThe University of Bergeneng
dc.subjectGrafalgoritmernb
dc.titleA 43k Kernel for Planar Dominating Set using Computer-Aided Reduction Rule Discoveryeng
dc.typeMaster thesiseng
dc.type.degreeMaster i Informatikkeng
dc.type.courseINF399eng
dc.subject.archivecodeMastergradeng
dc.subject.nus754199eng
dc.type.programMAMN-INFeng
dc.rights.holderCopyright the Author. All rights reservedeng
bora.peerreviewedNot peer reviewedeng
noa.realfagstermhttps://data.ub.uio.no/realfagstermer/c004774


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record