वृद्धिशील ग्राफ एल्गोरिदम

Question

कई बुनियादी ग्राफ एल्गोरिदम हैं जैसे टोपोलॉजिकल सॉर्ट, दृढ़ता से/कमजोर रूप से जुड़े घटक, सभी जोड़े/सिंगल-स्रोत सबसे कम पथ, पहुंच योग्यता आदि। इन एल्गोरिदम के बढ़ते रूपों में विभिन्न महत्वपूर्ण व्यावहारिक अनुप्रयोग हैं। "Incremental" से मेरा मतलब है कि उन ग्राफ़ एल्गोरिदम जो इनपुट आउटपुट में छोटे बदलावों (जैसे किनारे सम्मिलन और हटाना) को उनके आउटपुट में छोटे बदलावों की गणना कर सकते हैं, सबकुछ पुनः प्राप्त किए बिना। उदाहरण के लिए, एक कचरा कलेक्टर वैश्विक जड़ों से पहुंचने योग्य ढेर आवंटित ब्लॉक के उप-समूह को जमा करता है। हालांकि, मुझे डोमेन-विशिष्ट साहित्य (उदाहरण के लिए जीसी पर रिचर्ड जोन्स की नई पुस्तक) के बाहर चर्चा किए गए वृद्धिशील ग्राफ एल्गोरिदम के विषय को याद नहीं है।

मुझे वृद्धिशील ग्राफ एल्गोरिदम पर जानकारी कहां मिल सकती है या, उस मामले के लिए, सामान्य रूप से वृद्धिशील एल्गोरिदम?

Answer 1

1 999 से एपस्टीन, गैलील और इटालियनो द्वारा survey article है। वे वर्णन करेंगे कि आप "पूरी तरह गतिशील एल्गोरिदम" के रूप में क्या खोज रहे हैं; "आंशिक रूप से गतिशील एल्गोरिदम" को "वृद्धिशील एल्गोरिदम" में विभाजित किया जाता है, जो केवल प्रविष्टियां, और "घटती एल्गोरिदम" की अनुमति देता है, जो केवल हटाने को अनुमति देता है।

इसके अलावा, मुझे संदेह है कि आपको शोध साहित्य पढ़ना होगा - केवल कुछ मुट्ठी भर शोधकर्ता हैं जो गतिशील ग्राफ एल्गोरिदम पर काम करते हैं। सर्वेक्षण को उद्धृत करने वाले कागजात की जांच करके आपको लेख ढूंढने में सक्षम होना चाहिए।