Back to search

University of Ioannina

Algorithm design and engineering for graph connectivity problems

Abstract

dc:description

This dissertation deals with topics related to some notions of graph connectivity in directed graphs and mixed graphs. The edge and vertex connectivity of a graph are important measures of its resilience as a network. There is a great variety of real-life relations that can be modeled by graphs. A few of the most notable examples include road networks, the World Wide Web, social networks, and other communication networks. Such a graph may consist of millions of edges and vertices as for example road or social networks. Therefore, we are interested both in asymptotically fast algorithms and in algorithms that are efficient in practice. In this dissertation, we present efficient implementations and empirical studies of important algorithms for basic connectivity problems in directed graphs. Moreover, we propose efficient methods of speeding up these algorithms for practical instances, which improved their execution times by one to two orders of magnitude. Finally, we provide new linear-time algorithms for related connectivity problems in mixed graphs. Firstly we provide an experimental study of algorithms for computing the edge connectivity λ of a directed graph efficiently in practice. The edge connectivity λ of Gis the minimum number of edges whose deletion leaves G not strongly connected. A graph G is strongly connected if there is a directed path from each vertex to any other vertex. Computing the edge connectivity of a graph is a classical subject in graph theory, and is an important notion in several application areas, such as transportation, communication, production, scheduling, and power engineering. We presented the first efficient implementations of Gabow’s algorithm [1] which runs in O(λmlog n)time and is based on matroid intersection and packing spanning trees, as well as algorithms based on recent “local search” algorithms for minimum-cut which have been proposed by Chechik et al. [2] and Forster et al. [3], of complexity O(λ2mpolylogn).Also, we proposed practical methods for speeding up these algorithms. In the experimental study, the efficiency of the various algorithms was compared on real graphs, taken from various application areas, as well as on synthetic graphs, aiming to highlight the advantages and disadvantages of each technique. Then we studied the problem of packing arborescences. An s-arborescence of Gis a directed spanning tree, i.e., an acyclic subgraph of G where s has in-degree zero and every other vertex has in-degree one. The problem of packing arborescences is to compute a maximum cardinality set of edge-disjoint arborescences of a directed graph. We explored the design space of efficient algorithms for packing arborescences of a directed graph in practice and we conducted a thorough empirical study to highlight the merits and weaknesses of each technique. In particular, we presented efficient implementations of Gabow’s arborescence packing algorithm [1] of complexity O(k2n2), Tarjan’s algorithm [4] of complexity O(k2m2), and the algorithm of Tongand Lowler [5] of complexity O(k2mn). In addition, we proposed a simple but very efficient method that significantly improves the running time of Gabow’s algorithm in practice. In our experimental study, the performance of the various algorithms was compared on real-world taken from a wide range of applications, as well as on synthetic graphs. Finally, we considered some orientation problems in mixed graphs related to the concept of 2-edge strong connectivity. A mixed graph G is a graph that consists of both undirected and directed edges. An orientation of G is formed by orienting all the undirected edges of G, i.e., converting each undirected edge fu, vg into a directed edge that is either (u, v) or (v, u). Many mixed or undirected graph orientation problems have been studied in the literature, depending on the properties we wish a particular orientation to have. An orientation R of G is a strong orientation when the resulting graph is strongly connected. More generally, an orientation R of G isa k-strong orientation when the resulting graph is k-edge strongly connected. These concepts have applications in areas such as the design of road and telecommunications networks, and the structural stability of buildings. Our main result was to provide a linear time algorithm for the following problem. Given a mixed graph G, we wish to compute its maximal sets of vertices C1,C2, . . . ,Ck with the property that by removing any edge e from G (directed or undirected) there is an orientation Ri of Gne such that all vertices of Ci are strongly connected in Ri. This problem is related to 2-edge strong connectivity, since if G contains only directed edges, then every set Ci corresponds toa 2-edge strong component of G.

Degree

thesis:*
Grantor dc:publisher
University of Ioannina
Year dc:date
2024

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Kefallinos, Dionisios
  • Κεφαλληνός, Διονύσιος

Subjects

dc:subject × 10

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/57010

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Kefallinos, Dionisios; Κεφαλληνός, Διονύσιος. Algorithm design and engineering for graph connectivity problems. University of Ioannina, 2024. http://hdl.handle.net/10442/hedi/57010