वक्ता: डॉ. शैली वर्मा

वार्ता का शीर्षक : ग्राफ रंग में एल्गोरिथम प्रगति: ग्रंडी रंग पर ध्यान केंद्रित

तिथि, समय और स्थान: 10 जनवरी 2025, दोपहर 3:00 बजे से शाम 4:00 बजे तक, सेमिनार हॉल, गणित विभाग में।

सारांश: ग्राफ रंग शेड्यूलिंग, रजिस्टर आवंटन और आवृत्ति असाइनमेंट में कई अनुप्रयोगों के साथ कॉम्बिनेटरियल ऑप्टिमाइज़ेशन में एक केंद्रीय समस्या है। इस बात में, मैं ग्राफ रंग समस्याओं में अपने शोध योगदान पर ध्यान केंद्रित करूंगा, विशेष रूप से आंशिक ग्रंडी रंग समस्या की पैरामीटर जटिलता में मेरा हालिया काम। आंशिक ग्रंडी रंग समस्या का उद्देश्य किसी दिए गए ग्राफ के कोने को कुछ बाधाओं के तहत अधिकतम रंगों के साथ रंगना है। सामान्य रेखांकन के लिए बहुपद समय में इस समस्या को हल करना मुश्किल है। दूसरे शब्दों में, आंशिक ग्रंडी रंग सामान्य रेखांकन के लिए एनपी-हार्ड है। यह कम्प्यूटेशनल कठिनाई समस्या की पैरामीटर जटिलता पर मेरे शोध को प्रेरित करती है। पैरामीटरीकृत जटिलता विभिन्न समस्या मापदंडों के संबंध में उनकी अंतर्निहित कठिनाई के आधार पर कम्प्यूटेशनल समस्याओं को वर्गीकृत करती है।

इन कम्प्यूटेशनल चुनौतियों का समाधान करने के लिए, हाल ही में, मैंने (सह-लेखकों के साथ) आंशिक ग्रंडी रंग समस्या की पैरामीटर जटिलता का अध्ययन किया और दिखाया कि समस्या पैरामीटर के संबंध में "बहुपद समय" में हल करने योग्य है क्योंकि रंगों की संख्या का उपयोग किया जाता है। यह बात आंशिक ग्रंडी रंग समस्या के लिए एक निश्चित-पैरामीटर ट्रैक्टेबल एल्गोरिदम पेश करेगी, जो रंगों की संख्या से पैरामीटर किए जाने पर कुशल समाधान प्रदान करेगी। ये निष्कर्ष ग्राफ रंग की कम्प्यूटेशनल जटिलता की हमारी समझ को आगे बढ़ाते हैं।

शैली वर्मा जर्मनी में हासो प्लैटनर इंस्टीट्यूट में पोस्ट-डॉक्टरेट शोधकर्ता हैं। सैद्धांतिक कंप्यूटर विज्ञान में उनका शोध मोटे तौर पर ग्राफ एल्गोरिदम पर केंद्रित है। उनके शोध के हितों में पैरामीटराइज्ड जटिलता, सटीक एल्गोरिदम और ग्राफ सिद्धांत शामिल हैं। इससे पहले, उन्होंने चेन्नई में गणितीय विज्ञान संस्थान में पोस्टडॉक्टरल शोधकर्ता के रूप में काम किया। उन्होंने गणित विभाग, आईआईटी दिल्ली से पीएचडी प्राप्त की।