Projects per year
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.
Original language | English |
---|---|
Title of host publication | ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 |
Editors | Daniel Marx |
Publisher | ACM |
Pages | 1206-1225 |
Number of pages | 20 |
ISBN (Electronic) | 9781611976465 |
DOIs | |
Publication status | Published - 2021 |
MoE publication type | A4 Article in a conference publication |
Event | ACM-SIAM Symposium on Discrete Algorithms - Virtual, Online, Alexandria, United States Duration: 10 Jan 2021 → 13 Jan 2021 Conference number: 32 https://www.siam.org/conferences/cm/conference/soda21 |
Publication series
Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|
Conference
Conference | ACM-SIAM Symposium on Discrete Algorithms |
---|---|
Abbreviated title | SODA |
Country/Territory | United States |
City | Alexandria |
Period | 10/01/2021 → 13/01/2021 |
Internet address |
Fingerprint
Dive into the research topics of 'Vertex sparsification for edge connectivity'. Together they form a unique fingerprint.-
ALGOCom: Novel Algorithmic Techniques through the Lens of Combinatorics
Chalermsook, P., Franck, M., Jindal, G., Gadekar, A., Jiamjitrak, W., Khodamoradi, K., Orgo, L., Spoerhase, J. & Yingchareonthawornchai, S.
01/02/2018 → 31/01/2024
Project: EU: ERC grants
-
Combinatorics of Graph Packing and Online Binary Search Trees
Chalermsook, P., Franck, M., Gadekar, A., Jiamjitrak, W., Obscura Acosta, N. & Uniyal, S.
01/09/2017 → 31/08/2022
Project: Academy of Finland: Other research funding