Low-high orders of directed graphs (Master thesis)

Καρανάσιου, Αικατερίνη


A number of diverse natural or man-made systems are modeled as graphs, capturing both the structure and the dynamics of the underlying system. Examples include but are not limited to the world-wide web, transportation, communication and social networks, databases, biological systems, circuits, and the control-flow of computer programs. For this reason, graphs play an important role in many academic disciplines, including mathematics, computer science, and social sciences. Connectivity problems hold central role in the area of graph theory and graph algorithms, with numerous practical applications such as routing, navigation and reliable communication. In this thesis we deal with problems related to connectivity in directed graphs. A flow graph G = (V;E; s) is a directed graph with a distinguished start vertex s. The dominator tree D of G is a tree rooted at s, such that a vertex v is an ancestor of a vertex w if and only if all paths from s to w include v. The dominator tree is a central tool in program optimization and code generation, and has many applications in other diverse areas including constraint programming, circuit testing, biology, and in algorithms for graph connectivity problems. A low-high order of G is a preorder delta of D that certifies the correctness of D, and has further applications in connectivity and path-determination problems. In the first part of the thesis, we consider how to maintain efficiently a low-high order of a flow graph incrementally under edge insertions. We present two algorithms that run in O(mn) total time for a sequence of m edge insertions in an initially empty flow graph with n vertices. Moreover, we provide applications of this result to other incremental problems in directed graphs. In the second part of the thesis, we apply low-high orders to a type of network design problems. Given a directed graph G = (V;E), our goal is to compute the smallest spanning subgraph of G that maintains the 2-vertex-connectivity relations in G. First, we deal the case where G is 2-vertex-connected and we wish to compute the smallest 2-vertexconnected spanning subgraph of G. We provide provide a linear-time algorithm that computes a 2-approximation for this problem, improving significantly the best previous approximation ratio achievable in linear time which was 3. Then we deal with the more general case, where G is not 2-vertex-connected, and provide linear-time 6-approximation algorithms. We complement our theoretical study of the above problems with an extensive empirical evaluation of our algorithms, using large real-world graphs taken from a variety of application areas. The experimental results show that our algorithms are not only theoretically-efficient but also perform very well in practice.
Alternative title / Subtitle: incremental algorithms and applications
δυναμικοί αλγόριθμοι και εφαρμογές
Institution and School/Department of submitter: Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Subject classification: Directed graphs
Keywords: Συνεκτικότητα,Κατευθυνόμενα γραφήματα,Αραιά υπογραφήματα,Δυναμικοί αλγόριθμοι,Connectivity,Directed graph,Sparse subgraphs,Dynamic algorithms
URI: http://olympias.lib.uoi.gr/jspui/handle/123456789/27801
Appears in Collections:Διατριβές Μεταπτυχιακής Έρευνας (Masters)

Files in This Item:
File Description SizeFormat 
Μ.Ε. ΚΑΡΑΝΑΣΙΟΥ ΑΙΚΑΤΕΡΙΝΗ 2016.pdf1.5 MBAdobe PDFView/Open



 Please use this identifier to cite or link to this item:
http://olympias.lib.uoi.gr/jspui/handle/123456789/27801
  This item is a favorite for 0 people.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.