Document

**Published in:** LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

We revisit once more the problem of designing an oracle for answering connectivity queries in undirected graphs in the presence of vertex failures. Specifically, given an undirected graph G with n vertices and m edges and an integer d_⋆ ≪ n, the goal is to preprocess the graph in order to construct a data structure 𝒟 such that, given a set of vertices F with |F| = d ≤ d_⋆, we can derive an oracle from 𝒟 that can efficiently answer queries of the form "is x connected with y in G⧵F?". Very recently, Long and Saranurak (FOCS 2022) provided a solution to this problem that is almost optimal with respect to the preprocessing time, the space usage, the update time, and the query time. However, their solution is highly complicated, and it seems very difficult to be implemented efficiently. Furthermore, it does not settle the complexity of the problem in the regime where d_⋆ is a constant. Here, we provide a much simpler solution to this problem, that uses only textbook data structures. Our algorithm is deterministic, it has preprocessing time and space complexity O(d_⋆ m log n), update time O(d⁴ log n), and query time O(d). These bounds compare very well with the previous best, especially considering the simplicity of our approach. In fact, if we assume that d_⋆ is a constant (d_⋆ ≥ 4), then our algorithm provides some trade-offs that improve the state of the art in some respects. Finally, the data structure that we provide is flexible with respect to d_⋆: it can be adapted to increases and decreases, in time and space that are almost proportional to the change in d_⋆ and the size of the graph.

Evangelos Kosinas. Connectivity Queries Under Vertex Failures: Not Optimal, but Practical. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 75:1-75:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kosinas:LIPIcs.ESA.2023.75, author = {Kosinas, Evangelos}, title = {{Connectivity Queries Under Vertex Failures: Not Optimal, but Practical}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {75:1--75:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.75}, URN = {urn:nbn:de:0030-drops-187289}, doi = {10.4230/LIPIcs.ESA.2023.75}, annote = {Keywords: Graphs, Connectivity, Fault-Tolerant, Oracles} }

Document

**Published in:** LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

The notions of edge-cuts and k-edge-connected components are fundamental in graph theory with numerous practical applications. Very recently, the first linear-time algorithms for computing all the 3-edge cuts and the 4-edge-connected components of a graph have been introduced. In this paper we present carefully engineered implementations of these algorithms and evaluate their efficiency in practice, by performing a thorough empirical study using both real-world graphs taken from a variety of application areas, as well as artificial graphs. To the best of our knowledge, this is the first experimental study for these problems, which highlights the merits and weaknesses of each technique. Furthermore, we present an improved algorithm for computing the 4-edge-connected components of an undirected graph in linear time. The new algorithm uses only elementary data structures, and is implementable in the pointer machine model of computation.

Loukas Georgiadis, Giuseppe F. Italiano, and Evangelos Kosinas. Computing the 4-Edge-Connected Components of a Graph: An Experimental Study. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 60:1-60:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{georgiadis_et_al:LIPIcs.ESA.2022.60, author = {Georgiadis, Loukas and Italiano, Giuseppe F. and Kosinas, Evangelos}, title = {{Computing the 4-Edge-Connected Components of a Graph: An Experimental Study}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {60:1--60:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.60}, URN = {urn:nbn:de:0030-drops-169988}, doi = {10.4230/LIPIcs.ESA.2022.60}, annote = {Keywords: Connectivity Cuts, Edge Connectivity, Graph Algorithms} }

Document

**Published in:** LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

We present the first linear-time algorithm that computes the 4-edge-connected components of an undirected graph. Hence, we also obtain the first linear-time algorithm for testing 4-edge connectivity. Our results are based on a linear-time algorithm that computes the 3-edge cuts of a 3-edge-connected graph G, and a linear-time procedure that, given the collection of all 3-edge cuts, partitions the vertices of G into the 4-edge-connected components.

Loukas Georgiadis, Giuseppe F. Italiano, and Evangelos Kosinas. Computing the 4-Edge-Connected Components of a Graph in Linear Time. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 47:1-47:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{georgiadis_et_al:LIPIcs.ESA.2021.47, author = {Georgiadis, Loukas and Italiano, Giuseppe F. and Kosinas, Evangelos}, title = {{Computing the 4-Edge-Connected Components of a Graph in Linear Time}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {47:1--47:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-204-4}, ISSN = {1868-8969}, year = {2021}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.47}, URN = {urn:nbn:de:0030-drops-146286}, doi = {10.4230/LIPIcs.ESA.2021.47}, annote = {Keywords: Cuts, Edge Connectivity, Graph Algorithms} }

Document

**Published in:** LIPIcs, Volume 190, 19th International Symposium on Experimental Algorithms (SEA 2021)

We consider two problems regarding the computation of connectivity cuts in undirected graphs, namely identifying vertex-edge cut-pairs and identifying 2-edge cuts, and present an experimental study of efficient algorithms for their computation. In the first problem, we are given a biconnected graph G and our goal is to find all vertices v such that G⧵v is not 2-edge-connected, while in the second problem, we are given a 2-edge-connected graph G and our goal is to find all edges e such that G⧵e is not 2-edge-connected. These problems are motivated by the notion of twinless strong connectivity in directed graphs but are also of independent interest. Moreover, the computation of 2-edge cuts is a main step in algorithms that compute the 3-edge-connected components of a graph. In this paper, we present streamlined versions of two recent linear-time algorithms of Georgiadis and Kosinas that compute all vertex-edge cut-pairs and all 2-edge cuts, respectively. We compare the empirical performance of our vertex-edge cut-pairs algorithm with an alternative linear-time method that exploits the structure of the triconnected components of G. Also, we compare the empirical performance of our 2-edge cuts algorithm with the algorithm of Tsin, which was reported to be the fastest one among the previously existing for this problem. To that end, we conduct a thorough experimental study to highlight the merits and weaknesses of each technique.

Loukas Georgiadis, Konstantinos Giannis, Giuseppe F. Italiano, and Evangelos Kosinas. Computing Vertex-Edge Cut-Pairs and 2-Edge Cuts in Practice. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 20:1-20:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{georgiadis_et_al:LIPIcs.SEA.2021.20, author = {Georgiadis, Loukas and Giannis, Konstantinos and Italiano, Giuseppe F. and Kosinas, Evangelos}, title = {{Computing Vertex-Edge Cut-Pairs and 2-Edge Cuts in Practice}}, booktitle = {19th International Symposium on Experimental Algorithms (SEA 2021)}, pages = {20:1--20:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-185-6}, ISSN = {1868-8969}, year = {2021}, volume = {190}, editor = {Coudert, David and Natale, Emanuele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2021.20}, URN = {urn:nbn:de:0030-drops-137920}, doi = {10.4230/LIPIcs.SEA.2021.20}, annote = {Keywords: 2-Connectivity, Graph Algorithms, Split Components} }

Document

**Published in:** LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

A directed graph G = (V,E) is twinless strongly connected if it contains a strongly connected spanning subgraph without any pair of antiparallel (or twin) edges. The twinless strongly connected components (TSCCs) of a directed graph G are its maximal twinless strongly connected subgraphs. These concepts have several diverse applications, such as the design of telecommunication networks and the structural stability of buildings. A vertex v ∈ V is a twinless strong articulation point of G, if the deletion of v increases the number of TSCCs of G. Here, we present the first linear-time algorithm that finds all the twinless strong articulation points of a directed graph. We show that the computation of twinless strong articulation points reduces to the following problem in undirected graphs, which may be of independent interest: Given a 2-vertex-connected undirected graph H, find all vertices v for which there exists an edge e such that H⧵{v,e} is not connected. We develop a linear-time algorithm that not only finds all such vertices v, but also computes the number of edges e such that H⧵{v,e} is not connected. This also implies that for each twinless strong articulation point v which is not a strong articulation point in a strongly connected digraph G, we can compute the number of TSCCs in G⧵v.

Loukas Georgiadis and Evangelos Kosinas. Linear-Time Algorithms for Computing Twinless Strong Articulation Points and Related Problems. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 38:1-38:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{georgiadis_et_al:LIPIcs.ISAAC.2020.38, author = {Georgiadis, Loukas and Kosinas, Evangelos}, title = {{Linear-Time Algorithms for Computing Twinless Strong Articulation Points and Related Problems}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {38:1--38:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-173-3}, ISSN = {1868-8969}, year = {2020}, volume = {181}, editor = {Cao, Yixin and Cheng, Siu-Wing and Li, Minming}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.38}, URN = {urn:nbn:de:0030-drops-133820}, doi = {10.4230/LIPIcs.ISAAC.2020.38}, annote = {Keywords: 2-connectivity, cut pairs, strongly connected components} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail