• norsk
    • English
  • English 
    • norsk
    • English
  • Login
View Item 
  •   Home
  • Faculty of Mathematics and Natural Sciences
  • Department of Informatics
  • Department of Informatics
  • View Item
  •   Home
  • Faculty of Mathematics and Natural Sciences
  • Department of Informatics
  • Department of Informatics
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Kernelization of Vertex Cover by Structural Parameters

Strømme, Torstein Jarl Fagerbakke
Master thesis
Thumbnail
View/Open
136350237.pdf (943.2Kb)
URI
https://hdl.handle.net/1956/15802
Date
2015-08-03
Metadata
Show full item record
Collections
  • Department of Informatics [536]
Abstract
In the NP-complete problem Vertex Cover, one is given a graph G and an integer k and are asked whether there exists a vertex set S ⊆ V (G) with size at most k such that every edge of the graph is incident to a vertex in S. In this thesis we explore techniques to solve Vertex Cover using parameterized algorithms, with a particular focus on kernelization by structural parameters. We present two new polynomial kernels for Vertex Cover, one parameterized by the size of a minimum degree-2 modulator, and one parameterized by the size of a minimum pseudoforest modulator. A degree-2 modulator is a vertex set X ⊆ V (G) such that G-X has maximum degree two, and a pseudoforest modulator is a vertex set X ⊆ V (G) such that every connected component of G-X has at most one cycle. Specifically, we provide polynomial time algorithms that for an input graph G and an integer k, outputs a graph G' and an integer k' such that G has a vertex cover of size k if and only if G' has a vertex cover of size k'. Moreover, the number of vertices of G' is bounded by O(|X|^7) where |X| is the size of a minimum degree-2 modulator for G, or bounded by O(|X|^12) where |X| is the size a minimum pseudoforest modulator for G. Our result extends known results on structural kernelization for Vertex Cover.
Publisher
The University of Bergen
Copyright
Copyright the Author. All rights reserved

Contact Us | Send Feedback

Privacy policy
DSpace software copyright © 2002-2019  DuraSpace

Service from  Unit
 

 

Browse

ArchiveCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsDocument TypesJournalsThis CollectionBy Issue DateAuthorsTitlesSubjectsDocument TypesJournals

My Account

Login

Statistics

View Usage Statistics

Contact Us | Send Feedback

Privacy policy
DSpace software copyright © 2002-2019  DuraSpace

Service from  Unit