कनेक्टेड घटक को गतिशील रूप से

Question

डिज्जॉइंट-सेट डेटा संरचना का उपयोग करके आसानी से ग्राफ का कनेक्टेड घटक मिल सकता है। और, यह सिर्फ Incremental Connected Components का समर्थन करता है।

हालांकि, मेरे मामले में, हटाने के किनारे बहुत आम है, ताकि मैं एक एल्गोरिथ्म या नई संरचना कनेक्टेड घटक पूरी तरह से गतिशील (जोड़ने और बढ़त को हटाने सहित) बनाए रख सकते हैं रहा हूँ

धन्यवाद

Answer 1

Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity (Holm, de Lichtenberg and Thorup 2001) एक एल्गोरिदम देता है जो ओ (लॉग (एन)^2) एम (लॉग (एन)/लॉग लेने वाले प्रश्नों (अपडेट (एन)^2) के अपडेट (प्रविष्टियां और हटाने) के साथ किनारे सम्मिलन, हटाने और कनेक्टिविटी प्रश्नों के मनमाना अनुक्रम की अनुमति देता है। लॉग (एन))) समय, ग्राफ में शिखर की संख्या होने के साथ। इन समय सीमाओं का मानना ​​है कि ग्राफ कोई किनारों से शुरू होता है।

मैं केवल अपने 38 पृष्ठों के पहले 2 स्किम्ड, लेकिन हो सकता है नहीं है (भी) डर - कागज गतिशील रेखांकन (जो है, रेखांकन पर नए एल्गोरिदम का एक समूह है कि कुशलता से अधिक संशोधित किया जा सकता का वर्णन करता है समय) जिसमें कनेक्टिविटी सबसे सरल है।