dc.contributor.author Wingsternes, Thomas dc.date.accessioned 2018-08-16T16:04:20Z dc.date.available 2018-08-16T16:04:20Z dc.date.issued 2018-06-20 dc.date.submitted 2018-06-19T22:00:06Z dc.identifier.uri https://hdl.handle.net/1956/18135 dc.description.abstract In this thesis we shall study both the maximum number of minimal connected vertex covers and the maximum number of minimal independent feedback vertex sets in graphs. A subset S of the vertices of a graph G is a vertex cover if every edge in G is incident to some vertex in S. A vertex cover S in a graph G is a connected vertex cover if the subgraph of G induced by S is connected. A connected vertex cover S is a minimal connected vertex cover if no proper subset of S is also a connected vertex cover. A subset S of the vertices of a graph G is a feedback vertex set if the removal of S from G yields an acyclic graph. A feedback vertex set S in a graph G is an independent feedback vertex set if there are no edges in G which have both endpoints in S. An independent feedback vertex set S is a minimal independent feedback vertex set if no proper subset of S is also an independent feedback vertex set. Golovach et al.  showed that there are at most 1.8668^n minimal connected vertex covers in a graph on n vertices, and that these can be enumerated in time O(1.8668^n). Furthermore, it was shown by Agrawal et al.  that there are at most 1.7485^n minimal independent feedback vertex sets in a graph on n vertices. The authors of  also showed that this bound is algorithmic, that the set of all minimal independent feedback vertex sets in an n-vertex graph can be enumerated in time O*(1.7485n), where the O*-notation supresses polynomial factors. We present an upper bound 2 · 1.7076^n on the number of minimal connected vertex covers in a graph on n vertices. We also present new bounds on the maximum number of minimal independent feedback vertex sets in a graph. In particular, we show that for a graph on n vertices, there are at most 1.7229^n minimal independent feedback vertex sets, and that there exists an n-vertex graph which contains 1.5067^n minimal independent feedback vertex sets. We show that the upper bounds we achieve are algorithmic by presenting an algorithm which enumerates all minimal connected vertex covers in time O*(1.7076^n), and an algorithm which enumerates all minimal independent feedback vertex sets in time O*(1.7229^n), where n is the number of vertices in the input graph. en_US dc.language.iso eng eng dc.publisher The University of Bergen en_US dc.subject independent feedback vertex set eng dc.subject enumeration algorithms eng dc.subject combinatorial bounds eng dc.subject connected vertex cover eng dc.title Improved Combinatorial Bounds and Enumerators for the Connected Vertex Cover and Independent Feedback Vertex Set Problems en_US dc.type Master thesis dc.date.updated 2018-06-19T22:00:06Z 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-0
﻿