Show simple item record

dc.contributor.authorWingsternes, Thomas
dc.date.accessioned2018-08-16T16:04:20Z
dc.date.available2018-08-16T16:04:20Z
dc.date.issued2018-06-20
dc.date.submitted2018-06-19T22:00:06Z
dc.identifier.urihttps://hdl.handle.net/1956/18135
dc.description.abstractIn 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. [1] 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. [2] that there are at most 1.7485^n minimal independent feedback vertex sets in a graph on n vertices. The authors of [2] 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.isoengeng
dc.publisherThe University of Bergenen_US
dc.subjectindependent feedback vertex seteng
dc.subjectenumeration algorithmseng
dc.subjectcombinatorial boundseng
dc.subjectconnected vertex covereng
dc.titleImproved Combinatorial Bounds and Enumerators for the Connected Vertex Cover and Independent Feedback Vertex Set Problemsen_US
dc.typeMaster thesis
dc.date.updated2018-06-19T22:00:06Z
dc.rights.holderCopyright the Author. All rights reserveden_US
dc.description.degreeMasteroppgave i informatikken_US
dc.description.localcodeINF399
dc.subject.nus754199eng
fs.subjectcodeINF399
fs.unitcode12-12-0


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record