Key points are not available for this paper at this time.
हम शॉर्ट पाथ पैकिंग समस्या का अध्ययन करते हैं, जिसमें एक ग्राफ G, पूर्णांक k और वर्टिसेस s और t दिए जाने पर यह पूछा जाता है कि क्या k जोड़े में आंतरिक रूप से वर्टेक्स-डिसजॉइंट s-t पथ होते हैं जिनकी लंबाई अधिकतम होती है। यह समस्या NP-हार्ड साबित हुई है और इसे k द्वारा निश्चित-फैसे-ट्रेक्टेबल के रूप में वर्णित किया गया है। इस समस्या पर अधिकांश पूर्ववर्ती अनुसंधान सैद्धांतिक रहा है, जिसमें सीमित व्यावहारिक कार्यान्वयन हैं। हम एक सटीक FPT-अल्गोरिदम प्रस्तुत करते हैं जो खोज-ट्री दृष्टिकोण के साथ लालची स्थानीयकरण के संयोजन पर आधारित है। जबकि इसकी सबसे खराब स्थिति में समय जटिलता (k ²) ^k n^O (1) वर्तमान का स्तर से बड़ी है, खोज-ट्री एल्गोरिदम की प्रकृति संभावित अनुकूलनों की एक विस्तृत श्रृंखला की अनुमति देती है। हम इन संभावनाओं का लाभ उठाते हैं, जिसमें इनपुट पूर्व-प्रसंस्करण, तुच्छ और असंभव उदाहरणों की प्रारंभिक पहचान, और आशाजनक उपसमस्याओं का रणनीतिक चयन शामिल है। इन दृष्टिकोणों को विभिन्न ग्राफ के एक बड़े डेटासेट पर लागू और गहन परीक्षण किया गया। परिणाम दिखाते हैं कि हमारे ह्यूरिस्टिक सुधार बहुत प्रभावी हैं और इसे देखते हुए अधिकतर उदाहरणों में, हम तेज़ समय प्राप्त कर सकते हैं।
माइकल किरण ह्यूबर (मंगलवार,) ने इस प्रश्न का अध्ययन किया।