dc.contributor.author Skjørten, Ida Bredal dc.date.accessioned 2017-06-22T11:00:30Z dc.date.available 2017-06-22T11:00:30Z dc.date.issued 2017-06-20 dc.date.submitted 2017-06-19T22:00:13Z dc.identifier.uri https://hdl.handle.net/1956/16058 dc.description.abstract Graphs are mathematical objects that can be used to model many real world problems. An example is a roadmap, where the nodes in the graph represent cities and the edges of the graph represent roads. An interesting and important task is to find certain objects or node subsets with a specified property in a graph. It is exactly this type of question this thesis will study, and the objects that we are looking for are minimal connected dominating sets. In many applications the best known way to find a minimum object of a certain type can be to list all the minimal objects and then pick the smallest one among these minimal objects. Thus, knowing the number of such objects and being able to list them in reasonable time might help us get faster algorithms for hard problems. In 2015, Golovach, Heggernes and Kratsch gave an O(1.3803^n)-time algorithm for enumerating the mcds in split graphs. This algorithm gives the best known upper bound on the number of mcds in split graphs. Golovach et al also give the best known lower bound example on the number of mcds in split graphs, which has 1.3195^n mcds, so there is an albeit small gap between the lower and the upper bound. In this thesis we implement and test the mentioned enumeration algorithm, and with these tests we find a new lower bound example with 1.3195^n mcds. On the theoretical side, we improve the running time of the enumeration algorithm to O(1.3674^n), thereby proving that the maximum number of mcds in split graphs is at most 1.3674^n. Consequently, we narrow the gap between the known upper and lower bound on the maximum number of mcds in split graphs. en_US dc.language.iso eng eng dc.publisher The University of Bergen en_US dc.subject minimal connected dominating sets eng dc.subject split graphs eng dc.subject upper bound eng dc.subject lower bound eng dc.subject enumeration eng dc.title Faster enumeration of minimal connected dominating sets in split graphs en_US dc.type Master thesis dc.date.updated 2017-06-19T22:00:13Z dc.rights.holder Copyright the Author. All rights reserved en_US dc.description.degree Masteroppgave i informatikk en_US dc.description.localcode INF399 dc.subject.nus 754199 eng fs.subjectcode INF399 fs.unitcode 12-12-00
﻿