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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 1 سبتمبر 2022
الحدث30th Annual European Symposium on Algorithms, ESA 2022 - Berlin/Potsdam, ألمانيا
المدة: ٥ سبتمبر ٢٠٢٢٩ سبتمبر ٢٠٢٢

سلسلة المنشورات

الاسمLeibniz International Proceedings in Informatics, LIPIcs
مستوى الصوت244
رقم المعيار الدولي للدوريات (المطبوع)1868-8969


!!Conference30th 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'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا