Data Structures for Node Connectivity Queries

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים


Let κ (s, t) denote the maximum number of internally disjoint st-paths in an undirected graph G. We consider designing a data structure that includes a list of cuts, and answers the following query: given s, t ∈ V , determine whether κ(s, t) ≤ k, and if so, return a pointer to an st-cut of size ≤ k (or to a minimum st-cut) in the list. A trivial data structure that includes a list of n(n - 1)/2 cuts and requires Θ(kn2) space can answer each query in O(1) time. We obtain the following results. In the case when G is k-connected, we show that 2n cuts suffice, and that these cuts can be partitioned into 2k + 1 laminar families. Thus using space O(kn) we can answers each min-cut query in O(1) time, slightly improving and substantially simplifying the proof of a recent result of Pettie and Yin [18]. We then extend this data structure to subset k-connectivity. In the general case we show that (2k+1)n cuts suffice to return an st-cut of size ≤ k, and a list of size k(k+2)n contains a minimum st-cut for every s, t ∈ V . Combining our subset k-connectivity data structure with the data structure of Hsu and Lu [7] for checking k-connectivity, we give an O(k2n) space data structure that returns an st-cut of size ≤ k in O(log k) time, while O(k3n) space enables to return a minimum st-cut.

שפה מקוריתאנגלית
כותר פרסום המארחESA
עורכיםShiri Chechik, Gonzalo Navarro, Eva Rotenberg, Grzegorz Herman
מוציא לאורSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
מספר עמודים12
מסת"ב (אלקטרוני)9783959772471
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1 ספט׳ 2022
אירוע30th Annual European Symposium on Algorithms, ESA 2022 - Berlin/Potsdam, גרמניה
משך הזמן: 5 ספט׳ 20229 ספט׳ 2022

סדרות פרסומים

שםLeibniz International Proceedings in Informatics, LIPIcs
ISSN (מודפס)1868-8969


כנס30th Annual European Symposium on Algorithms, ESA 2022

הערה ביבליוגרפית

Publisher Copyright:
© 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Data Structures for Node Connectivity Queries'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי