University of Ioannina
Efficient algorithms for some connectivity problems, in static and dynamic graphs
Abstract
dc:descriptionIn 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- Αλγόριθμοι
- Δομές δεδομένων
- Γραφήματα
- Συνεκτικότητα
- Algorithms
- Data structures
- Graphs
- Connectivity
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Φυσικές Επιστήμες
- Επιστήμη ηλεκτρονικών υπολογιστών, θεωρία και μέθοδοι
- Μαθηματικά
- Μαθηματικά, γενικά
- Computer and Information Sciences
- Natural Sciences
- Computer science, theory and methods
- Mathematics
- Mathematics, general
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/55974