Vertex sparsification for edge connectivity
Loading...
Access rights
openAccess
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
20
Series
ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, pp. 1206-1225, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Abstract
Graph compression or sparsification is a basic information-theoretic and computational question. A major open problem in this research area is whether (1 + ε)-approximate cut-preserving vertex sparsifiers with size close to the number of terminals exist. As a step towards this goal, we study a thresholded version of the problem: for a given parameter c, find a smaller graph, which we call connectivity-c mimicking network, which preserves connectivity among k terminals exactly up to the value of c. We show that connectivity-c mimicking networks with O(kc4) edges exist and can be found in time m(c log n)O(c). We also give a separate algorithm that constructs such graphs with k · O(c)2c edges in time mcO(c) logO(1) n. These results lead to the first data structures for answering fully dynamic offline c-edge-connectivity queries for c ≥ 4 in polylogarithmic time per query, as well as more efficient algorithms for survivable network design on bounded treewidth graphs.Description
| openaire: EC/H2020/759557/EU//ALGOCom
Keywords
Other note
Citation
Chalermsook, P, Das, S, Kook, Y, Laekhanukit, B, Liu, Y P, Peng, R, Sellke, M & Vaz, D 2021, Vertex sparsification for edge connectivity. in D Marx (ed.), ACM-SIAM Symposium on Discrete Algorithms, SODA 2021. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, pp. 1206-1225, ACM-SIAM Symposium on Discrete Algorithms, Alexandria, Virginia, United States, 10/01/2021. https://doi.org/10.1137/1.9781611976465.74