Safe solutions for walks on graphs

Show full item record

Title: Safe solutions for walks on graphs
Author: Obscura Acosta, Nidia
Contributor: University of Helsinki, Faculty of Science
Thesis level: master's thesis
Abstract: In this thesis we study the concept of “safe solutions” in different problems whose solutions are walks on graphs. A safe solution to a problem X can be understood as a partial solution common to all solutions to problem X. In problems whose solutions are walks on graphs, safe solutions refer to walks common to all walks which are solutions to the problem. In this thesis, we focused on formulating four main graph traversal problems and finding characterizations for those walks contained in all their solutions. We give formulations for these graph traversal problems, we prove some of their combinatorial and structural properties, and we give safe and complete algorithms for finding their safe solutions based on their characterizations. We use the genome assembly problem and its applications as our main motivating example for finding safe solutions in these graph traversal problems. We begin by motivating and exemplifying the notion of safe solutions through a problem on s-t paths in undirected graphs with at least two non-trivial biconnected components S and T and with s ∈ S, t ∈ T . We continue by reviewing similar and related notions in other fields, especially in combinatorial optimization and previous work on the bioinformatics problem of genome assembly. We then proceed to characterize the safe solutions to the Eulerian cycle problem, where one must find a circular walk in a graph G which traverses each edge exactly once. We suggest a characterization for them by improving on (Nagarajan, Pop, JCB 2009) and a polynomial-time algorithm for finding them. We then study edge-covering circular walks in a graph G. We look at the characterization from (Tomescu, Medvedev, JCB 2017) for their safe solutions and their suggested polynomial-time algorithm and we show an optimal O(mn)-time algorithm that we proposed in (Cairo et al. CPM 2017). Finally, we generalize this to edge-covering collections of circular walks. We characterize safe solutions in an edge-covering setting and provide a polynomial-time algorithm for computing them. We suggested these originally in (Obscura et al. ALMOB 2018).
URI: URN:NBN:fi:hulib-201804131687
Date: 2018-04-16
Discipline: Algorithms and Machine Learning

Files in this item

Total number of downloads: Loading...

Files Size Format View
zzzzz.pdf 1.129Mb PDF View/Open

This item appears in the following Collection(s)

Show full item record