Back to search

University of Ioannina

Efficient algorithms for some connectivity problems, in static and dynamic graphs

Abstract

dc:description

In this thesis, we provide efficient algorithms for some connectivity problems in undirected graphs, in the static, dynamic, and sensitivity setting. Our contribution can be summarized as follows. (1) We provide the first linear-time algorithms for computing the 4- and 5-edge-connected components in undirected multigraphs. This result answers a theoretical question, and sheds light on the possibility that a linear-time solution may exist for general k. Furthermore, the algorithms that we provide can have a very efficient implementation with the use of elementary data structures. Especially for the case k=5, we provide a novel analysis of the structure of 4-edge cuts in 3-edge-connected graphs, that can guide us into a proper selection of them for our purposes. We believe that this analysis may provide a clue for a general solution for the k-edge-connected components, or other related graph connectivity problems. (2) A key component in our algorithm for the case k=5 is an oracle for answering connectivity queries for pairs of vertices in the presence of at most four edge-failures. Specifically, the oracle has size O(n), it can be constructed in linear time, and it answers connectivity queries in the presence of at most four edge-failures in constant time, where n denotes the number of vertices of the graph. We note that this is a result of independent interest. (3) We provide an oracle for efficiently answering connectivity queries in the presence of vertex failures. Specifically, we design a data structure that can handle an arbitrary but fixed number of vertex failures, so that it can efficiently answer connectivity queries between vertices in the remaining graph. This very basic connectivity problem has received the attention of researchers for more than a decade now, but the solutions that have been provided are highly complicated and very difficult to be implemented efficiently. On the other hand, our solution is arguably the simplest that has been proposed for this problem; it is relatively easy to describe and analyze, and it uses only standard textbook data structures. Furthermore, it even provides some trade-offs that improve on the state of the art in some respects. (4) Finally, we deal with the computation of the maximal k-edge-connected subgraphs in incremental graphs. We provide a general framework that reduces this computation to the incremental maintenance of the k-edge-connected components. As a concrete application of this framework, we provide an algorithm for the incremental maintenance of the maximal 3-edge-connected subgraphs, by relying on algorithms and data structures for the incremental maintenance of the 3-edge-connected components. This provides a significant improvement over the state of the art, which is given by applying the best known static algorithm after every insertion. Furthermore, we provide fast constructions of sparse spanning subgraphs that have the same maximal k-edge-connected subgraphs as the original graph. These can be used in order to speed up computations that involve the maximal k-edge-connected subgraphs.

Degree

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

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Kosinas, Evangelos
  • Κοσίνας, Ευάγγελος

Subjects

dc:subject × 18

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/55974

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

Kosinas, Evangelos; Κοσίνας, Ευάγγελος. Efficient algorithms for some connectivity problems, in static and dynamic graphs. University of Ioannina, 2024. http://hdl.handle.net/10442/hedi/55974