This is a good article. Click here for more information.

फीडबैक आर्क सेट: Difference between revisions

From Vigyanwiki
No edit summary
Line 28: Line 28:
किसी दिए गए ग्राफ़ का फीडबैक चाप समुच्चय <math>G</math> दिष्ट रेखा ग्राफ़ के फीडबैक शीर्ष समुच्चय के समान है {{nowrap|of <math>G</math>.}} यहां, एक फीडबैक वर्टेक्स समुच्चय को फीडबैक चाप समुच्चय के अनुरूप परिभाषित किया गया है, ग्राफ के शीर्षों के एक उपसमुच्चय के रूप में जिसका विलोपन सभी चक्रों को खत्म कर देगा। दिष्ट ग्राफ़ का रेखा ग्राफ़ <math>G</math> प्रत्येक किनारे के लिए एक शीर्ष है {{nowrap|of <math>G</math>,}} और प्रत्येक दो-किनारे पथ के लिए एक किनारा {{nowrap|in <math>G</math>.}} दूसरी दिशा में, किसी दिए गए ग्राफ़ का न्यूनतम फीडबैक शीर्ष समुच्चय <math>G</math> के प्रत्येक शीर्ष को विभाजित करके प्राप्त ग्राफ़ पर न्यूनतम फीडबैक चाप समुच्चय समस्या का समाधान प्राप्त किया जा सकता है <math>G</math> दो शीर्षों में, एक आने वाले किनारों के लिए और एक बाहर जाने वाले किनारों के लिए। ये परिवर्तन फीडबैक चाप समुच्चय और फीडबैक वर्टेक्स समुच्चय के लिए सटीक एल्गोरिदम को उनकी जटिलता सीमाओं के उचित अनुवाद के साथ एक-दूसरे में परिवर्तित करने की अनुमति देते हैं। हालाँकि, यह परिवर्तन अधिकतम अचक्रीयउपग्राफ समस्या के लिए सन्निकटन गुणवत्ता को संरक्षित नहीं करता है।{{r|enss|Hecht}}
किसी दिए गए ग्राफ़ का फीडबैक चाप समुच्चय <math>G</math> दिष्ट रेखा ग्राफ़ के फीडबैक शीर्ष समुच्चय के समान है {{nowrap|of <math>G</math>.}} यहां, एक फीडबैक वर्टेक्स समुच्चय को फीडबैक चाप समुच्चय के अनुरूप परिभाषित किया गया है, ग्राफ के शीर्षों के एक उपसमुच्चय के रूप में जिसका विलोपन सभी चक्रों को खत्म कर देगा। दिष्ट ग्राफ़ का रेखा ग्राफ़ <math>G</math> प्रत्येक किनारे के लिए एक शीर्ष है {{nowrap|of <math>G</math>,}} और प्रत्येक दो-किनारे पथ के लिए एक किनारा {{nowrap|in <math>G</math>.}} दूसरी दिशा में, किसी दिए गए ग्राफ़ का न्यूनतम फीडबैक शीर्ष समुच्चय <math>G</math> के प्रत्येक शीर्ष को विभाजित करके प्राप्त ग्राफ़ पर न्यूनतम फीडबैक चाप समुच्चय समस्या का समाधान प्राप्त किया जा सकता है <math>G</math> दो शीर्षों में, एक आने वाले किनारों के लिए और एक बाहर जाने वाले किनारों के लिए। ये परिवर्तन फीडबैक चाप समुच्चय और फीडबैक वर्टेक्स समुच्चय के लिए सटीक एल्गोरिदम को उनकी जटिलता सीमाओं के उचित अनुवाद के साथ एक-दूसरे में परिवर्तित करने की अनुमति देते हैं। हालाँकि, यह परिवर्तन अधिकतम अचक्रीयउपग्राफ समस्या के लिए सन्निकटन गुणवत्ता को संरक्षित नहीं करता है।{{r|enss|Hecht}}


[[File:Scc-1.svg|thumb|upright=1.35|तीन मजबूती से जुड़े घटकों के साथ एक दिष्ट ग्राफ, जिनमें से सबसे दाहिनी ओर को आर्टिक्यूलेशन वर्टेक्स पर विभाजित किया जा सकता है <math>d</math> दो द्वि-जुड़े घटकों में, प्रत्येक दो शीर्षों का एक चक्र। फीडबैक चाप समुच्चय समस्या को प्रत्येक मजबूती से जुड़े घटक में और मजबूती से जुड़े घटक के प्रत्येक द्वि-कनेक्टेड घटक में अलग से हल किया जा सकता है।]]फीडबैक चाप समुच्चय समस्या के सटीक और अनुमानित दोनों समाधानों में, दिए गए ग्राफ़ के प्रत्येक मजबूती से जुड़े घटक को अलग से हल करना और इन दृढ़ता से जुड़े घटकों को आर्टिक्यूलेशन शीर्षों पर विभाजित करके उनके द्वि-जुड़े घटकों को और भी दूर तक तोड़ना पर्याप्त है। इन उपसमस्याओं में से किसी एक के भीतर समाधान का चुनाव दूसरों को प्रभावित नहीं करता है, और जो किनारे इनमें से किसी भी घटक में दिखाई नहीं देते हैं वे फीडबैक चाप समुच्चय में शामिल करने के लिए बेकार हैं।{{r|pa92}} जब इन घटकों में से एक को दो शीर्षों को हटाकर दो डिस्कनेक्ट किए गए उपग्राफ में अलग किया जा सकता है, तो एक अधिक जटिल अपघटन लागू होता है, जिससे समस्या को इसके दृढ़ता से जुड़े घटकों के एसपीक्यूआर पेड़ से प्राप्त उप-समस्याओं में विभाजित किया जा सकता है।{{r|np00}}
[[File:Scc-1.svg|thumb|upright=1.35|तीन [[दृढ़ता से जुड़े घटकों|दृढ़ता से संयोजित घटकों]] के साथ एक दिष्ट ग्राफ, जिनमें से सबसे दाहिनी ओर को आर्टिक्यूलेशन शीर्ष <math>d</math> पर [[द्वियोजी]] [[घटकों]] में विभाजित किया जा सकता है, प्रत्येक दो शीर्षों का एक चक्र है। फीडबैक चाप समुच्चय समस्या को प्रत्येक मजबूती से जुड़े घटक में और मजबूती से जुड़े घटक के प्रत्येक द्वि-कनेक्टेड घटक में अलग से हल किया जा सकता है।]]फीडबैक चाप समुच्चय समस्या के सटीक और अनुमानित दोनों समाधानों में, दिए गए ग्राफ़ के प्रत्येक मजबूती से जुड़े घटक को अलग से हल करना और इन दृढ़ता से जुड़े घटकों को आर्टिक्यूलेशन शीर्षों पर विभाजित करके उनके द्वि-जुड़े घटकों को और भी दूर तक तोड़ना पर्याप्त है। इन उपसमस्याओं में से किसी एक के भीतर समाधान का चुनाव दूसरों को प्रभावित नहीं करता है, और जो किनारे इनमें से किसी भी घटक में दिखाई नहीं देते हैं वे फीडबैक चाप समुच्चय में शामिल करने के लिए बेकार हैं।{{r|pa92}} जब इन घटकों में से एक को दो शीर्षों को हटाकर दो डिस्कनेक्ट किए गए उपग्राफ में अलग किया जा सकता है, तो एक अधिक जटिल अपघटन लागू होता है, जिससे समस्या को इसके दृढ़ता से जुड़े घटकों के एसपीक्यूआर पेड़ से प्राप्त उप-समस्याओं में विभाजित किया जा सकता है।{{r|np00}}


===सटीक===
===सटीक===

Revision as of 22:36, 15 July 2023

एक दिष्ट ग्राफ़ का न्यूनतम फीडबैक चाप समुच्चय (लाल डैशित किनारे) और अधिकतम अचक्रीय उपग्राफ (नीला ठोस किनारा) में विभाजन

ग्राफ़ सिद्धांत और ग्राफ एल्गोरिथ्म में, एक दिष्ट ग्राफ में फीडबैक चाप समुच्चय या फीडबैक किनारा समुच्चय ग्राफ़ के किनारों का एक उपसमूह होता है जिसमें ग्राफ़ के प्रत्येक चक्र में से कम से कम एक किनारा होता है। ग्राफ़ से इन किनारों को हटाने से सभी चक्र टूट जाते हैं, जिससे एक दिष्ट अचक्रीय ग्राफ बनता है, जो दिए गए ग्राफ़ का एक अचक्रीय उपग्राफ होता है। सबसे कम संभावित किनारों के साथ समुच्चय किया गया फीडबैक चाप न्यूनतम फीडबैक चाप समुच्चय है और इसका अपनेय (रिमूवल) अधिकतम अचक्रीय उपग्राफ छोड़ता है; इन इष्टमीकरण समस्याओं के भारित संस्करणों का भी उपयोग किया जाता है। यदि फीडबैक चाप समुच्चय न्यूनतम है, जिसका अर्थ है कि इसमें से किसी भी किनारे को हटाने से एक उपसमुच्चय उत्पन्न होता है जो फीडबैक चाप समुच्चय नहीं है, तो इसमें एक अतिरिक्त गुण होता है: इसके सभी किनारों को हटाने के बजाय उन्हें उत्क्रमी करने से एक दिष्ट अचक्रीय ग्राफ बनता है।

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

एक निकट से संबंधित समस्या, फीडबैक शीर्ष समुच्चय, एक दिष्ट या अदिष्‍ट ग्राफ में प्रत्येक चक्र से कम से कम एक शीर्ष युक्त शीर्षों का एक समुच्चय है। अदिष्‍ट ग्राफों में, विस्तरित वृक्ष सबसे बड़े चक्रीय उपग्राफ होते हैं, और एक विस्तरित वृक्ष को बनाने में हटाए गए किनारों की संख्या परिपथ कोटि होती है।

अनुप्रयोग

2016 ओलंपिक में पुरुषों के बीच वॉलीबॉल के स्कोर, पूल एफ, और इन स्कोरों के लिए न्यूनतम-अपसैट (परिवर्तन) रैंकिंग थी। प्रत्येक मैच में हारने वाले से विजेता की ओर तीर लगाए जाते हैं, और जब परिणाम रैंकिंग के अनुरूप होता है तो उन्हें नीला रंग दिया जाता है और परिवर्तन के लिए लाल रंग दिया जाता है, जो परिणाम रैंकिंग के साथ असंगत होता है। इस रैंकिंग के साथ, केवल एक मैच परिवर्तन वाला है, जिसमें यूएसए ने क्यूएटी को हराया था। ओलंपिक में उपयोग की जाने वाली वास्तविक रैंकिंग निर्धारित अनुपात पर ईएसपी को क्यूएटी से आगे रखने से भिन्न थी, जिससे उनके मैच को एक और परिवर्तन के रूप में स्थान दिया गया।[1]

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

  • राउंड-रॉबिन टूर्नामेंट राउंड-रॉबिन खेल वाली खेल प्रतियोगिताओं में, प्रत्येक गेम के परिणामों को प्रत्येक गेम के हारने वाले से विजेता की ओर दिष्ट करके दर्ज किया जा सकता है। परिणामी ग्राफ़ में न्यूनतम फीडबैक चाप समुच्चय ढूंढना, उसके किनारों को उलटना, और टोपोलॉजिकल ऑर्डरिंग, सभी प्रतिस्पर्धियों पर एक रैंकिंग तैयार करता है। रैंकिंग चुनने के विभिन्न तरीकों के बीच, यह उलटफेर की कुल संख्या को कम करता है, ऐसे खेल जिनमें कम रैंक वाले प्रतियोगी ने उच्च रैंक वाले प्रतियोगी को हराया।[2][3][4] कई खेल प्रत्येक खेल के लिए दिए गए अंकों के आधार पर समूह टूर्नामेंट रैंकिंग प्रणाली के लिए सरल तरीकों का उपयोग करते हैं;[5] ये विधियां न्यूनतम-अपसमुच्चय रैंकिंग का निरंतर अनुमान प्रदान कर सकती हैं।[6]
  • प्राइमेटोलॉजी में और आम तौर पर एथोलॉजी में, प्रभुत्व पदानुक्रम अक्सर देखे गए प्रभुत्व व्यवहार में सबसे कम उलटफेर के साथ एक आदेश की खोज करके निर्धारित किया जाता है, जो न्यूनतम फीडबैक चाप समुच्चय समस्या का दूसरा रूप है।[7][8][9]
  • गणितीय मनोविज्ञान में, किसी दिए गए मानदंड के अनुसार विषयों की वस्तुओं के समुच्चय की रैंकिंग निर्धारित करना दिलचस्प है, जैसे कि उनकी प्राथमिकता या आकार की उनकी धारणा, वस्तुओं के सभी जोड़े के बीच जोड़ीदार तुलना के आधार पर। टूर्नामेंट ग्राफ़ में निर्धारित न्यूनतम फीडबैक चाप एक रैंकिंग प्रदान करता है जो यथासंभव कुछ जोड़ीदार परिणामों से असहमत होता है।[2][10] वैकल्पिक रूप से, यदि इन तुलनाओं के परिणामस्वरूप प्रत्येक जोड़ीवार क्रम के लिए स्वतंत्र संभावनाएं होती हैं, तो समग्र रैंकिंग की अधिकतम संभावना का अनुमान इन संभावनाओं को संभावना फ़ंक्शन | लॉग-संभावनाओं में परिवर्तित करके और परिणामी में न्यूनतम-भार फीडबैक चाप समुच्चय ढूंढकर प्राप्त किया जा सकता है। टूर्नामेंट.[2][3]
  • समान अधिकतम-संभावना क्रम का उपयोग सीरिएशन (सांख्यिकी), आंकड़ों में समस्या और तत्वों को रैखिक क्रम में व्यवस्थित करने के खोजपूर्ण डेटा विश्लेषण के लिए किया जा सकता है, ऐसे मामलों में जहां डेटा उपलब्ध है जो तत्वों के बीच जोड़ीदार तुलना प्रदान करता है।[3][11][12]
  • रैंकिंग वोटिंग में, केमेनी-यंग पद्धति को एक ऐसे क्रम की तलाश के रूप में वर्णित किया जा सकता है जो उस जोड़ी के लिए विपरीत क्रम को पसंद करने वाले मतदाताओं की संख्या के उम्मीदवारों के जोड़े के योग को कम करता है।[13] इसे न्यूनतम-वजन फीडबैक चाप समुच्चय समस्या के रूप में तैयार और हल किया जा सकता है, जिसमें कोने उम्मीदवारों का प्रतिनिधित्व करते हैं, किनारों को प्रत्येक आमने-सामने की प्रतियोगिता के विजेता का प्रतिनिधित्व करने के लिए दिष्ट किया जाता है, और प्रत्येक किनारे की लागत संख्या का प्रतिनिधित्व करती है आमने-सामने हारने वाले को ऊंची रैंकिंग देने से मतदाता नाखुश हो जाएंगे।[14]

फीडबैक चाप समुच्चय का एक और प्रारंभिक अनुप्रयोग अनुक्रमिक लॉजिक सर्किट के डिजाइन से संबंधित है, जिसमें सिग्नल हमेशा इनपुट से आउटपुट तक बढ़ने के बजाय सर्किट के माध्यम से चक्र में फैल सकते हैं। ऐसे सर्किट में, न्यूनतम फीडबैक चाप समुच्चय उन बिंदुओं की संख्या को दर्शाता है जिन पर सूचना के नुकसान के बिना संकेतों को प्रसारित करने की अनुमति देने के लिए प्रवर्धन आवश्यक है।[15] एसिंक्रोनस घटकों से बने तुल्यकालिक सर्किट में, फीडबैक चाप समुच्चय के किनारों पर क्लॉक्ड गेट लगाकर सिंक्रोनाइज़ेशन प्राप्त किया जा सकता है।[16] इसके अतिरिक्त, एक फीडबैक चाप समुच्चय पर एक सर्किट को काटने से शेष सर्किट संयोजन तर्क में कम हो जाता है, जिससे इसका विश्लेषण सरल हो जाता है, और फीडबैक चाप समुच्चय का आकार नियंत्रित करता है कि कट में सर्किट के व्यवहार को समझने के लिए कितने अतिरिक्त विश्लेषण की आवश्यकता है।[15] इसी तरह, केमिकल इंजीनियरिंग में प्रक्रिया फ़्लोशीटिंग में, फीडबैक चाप समुच्चय पर प्रोसेस फ्लो आरेख के किनारों को तोड़ना, और उन किनारों पर मूल्यों के लिए सभी संभावनाओं का अनुमान लगाना या प्रयास करना, बाकी प्रक्रिया को व्यवस्थित तरीके से विश्लेषण करने की अनुमति देता है क्योंकि इसकी चक्रीयता का. इस एप्लिकेशन में, किनारों को इस तरह से तोड़ने के विचार को फाड़ना कहा जाता है।[17]

स्तरित ग्राफ ड्राइंग में, किसी दिए गए दिष्ट ग्राफ के शीर्षों को उपसमुच्चय (ड्राइंग की परतें) के एक क्रमबद्ध अनुक्रम में विभाजित किया जाता है, और प्रत्येक उपसमुच्चय को इस ड्राइंग की क्षैतिज रेखा के साथ रखा जाता है, जिसके किनारे ऊपर और नीचे की ओर बढ़ते हैं। परतें. इस प्रकार की ड्राइंग में, यह वांछनीय है कि अधिकांश या सभी किनारों को ऊपर और नीचे के किनारों को मिलाने के बजाय लगातार नीचे की ओर उन्मुख किया जाए, ताकि ड्राइंग में रीचैबिलिटी संबंध अधिक स्पष्ट रूप से स्पष्ट हो सकें। यह एक न्यूनतम या न्यूनतम फीडबैक चाप समुच्चय ढूंढकर, उस समुच्चय में किनारों को उलट कर, और फिर परतों में विभाजन को इस तरह से चुनकर प्राप्त किया जाता है जो परिणामी अचक्रीयग्राफ के टोपोलॉजिकल क्रम के अनुरूप हो।[18][19] फीडबैक चाप समुच्चय का उपयोग स्तरित ग्राफ ड्राइंग की एक अलग उपसमस्या के लिए भी किया गया है, परतों के लगातार जोड़े के भीतर शीर्षों का क्रम।[20]

ऑपरेटिंग सिस्टम में गतिरोध समाधान में, गतिरोध को तोड़ने के लिए निर्भरता की सबसे छोटी संख्या को हटाने की समस्या को न्यूनतम फीडबैक चाप समुच्चय खोजने में से एक के रूप में तैयार किया जा सकता है।[21][22] हालाँकि, इस समुच्चय को खोजने की कम्प्यूटेशनल कठिनाई और ऑपरेटिंग सिस्टम घटकों के भीतर गति की आवश्यकता के कारण, इस एप्लिकेशन में अक्सर सटीक एल्गोरिदम के बजाय अनुमान का उपयोग किया जाता है।[22]

एल्गोरिदम

समतुल्यताएं

सटीक अनुकूलन के प्रयोजनों के लिए न्यूनतम फीडबैक चाप समुच्चय और अधिकतम अचक्रीयउपग्राफ समतुल्य हैं, क्योंकि एक दूसरे का पूरक समुच्चय है। हालाँकि, पैरामीटरयुक्त जटिलता और सन्निकटन के लिए, वे भिन्न होते हैं, क्योंकि उन प्रकार के एल्गोरिदम के लिए उपयोग किया जाने वाला विश्लेषण समाधान के आकार पर निर्भर करता है, न कि केवल इनपुट ग्राफ़ के आकार पर, और न्यूनतम फीडबैक चाप समुच्चय और अधिकतम अचक्रीयउपग्राफ अलग-अलग होते हैं एक दूसरे से आकार.[23]

किसी दिए गए ग्राफ़ का फीडबैक चाप समुच्चय दिष्ट रेखा ग्राफ़ के फीडबैक शीर्ष समुच्चय के समान है of . यहां, एक फीडबैक वर्टेक्स समुच्चय को फीडबैक चाप समुच्चय के अनुरूप परिभाषित किया गया है, ग्राफ के शीर्षों के एक उपसमुच्चय के रूप में जिसका विलोपन सभी चक्रों को खत्म कर देगा। दिष्ट ग्राफ़ का रेखा ग्राफ़ प्रत्येक किनारे के लिए एक शीर्ष है of , और प्रत्येक दो-किनारे पथ के लिए एक किनारा in . दूसरी दिशा में, किसी दिए गए ग्राफ़ का न्यूनतम फीडबैक शीर्ष समुच्चय के प्रत्येक शीर्ष को विभाजित करके प्राप्त ग्राफ़ पर न्यूनतम फीडबैक चाप समुच्चय समस्या का समाधान प्राप्त किया जा सकता है दो शीर्षों में, एक आने वाले किनारों के लिए और एक बाहर जाने वाले किनारों के लिए। ये परिवर्तन फीडबैक चाप समुच्चय और फीडबैक वर्टेक्स समुच्चय के लिए सटीक एल्गोरिदम को उनकी जटिलता सीमाओं के उचित अनुवाद के साथ एक-दूसरे में परिवर्तित करने की अनुमति देते हैं। हालाँकि, यह परिवर्तन अधिकतम अचक्रीयउपग्राफ समस्या के लिए सन्निकटन गुणवत्ता को संरक्षित नहीं करता है।[21][24]

तीन दृढ़ता से संयोजित घटकों के साथ एक दिष्ट ग्राफ, जिनमें से सबसे दाहिनी ओर को आर्टिक्यूलेशन शीर्ष पर द्वियोजी घटकों में विभाजित किया जा सकता है, प्रत्येक दो शीर्षों का एक चक्र है। फीडबैक चाप समुच्चय समस्या को प्रत्येक मजबूती से जुड़े घटक में और मजबूती से जुड़े घटक के प्रत्येक द्वि-कनेक्टेड घटक में अलग से हल किया जा सकता है।

फीडबैक चाप समुच्चय समस्या के सटीक और अनुमानित दोनों समाधानों में, दिए गए ग्राफ़ के प्रत्येक मजबूती से जुड़े घटक को अलग से हल करना और इन दृढ़ता से जुड़े घटकों को आर्टिक्यूलेशन शीर्षों पर विभाजित करके उनके द्वि-जुड़े घटकों को और भी दूर तक तोड़ना पर्याप्त है। इन उपसमस्याओं में से किसी एक के भीतर समाधान का चुनाव दूसरों को प्रभावित नहीं करता है, और जो किनारे इनमें से किसी भी घटक में दिखाई नहीं देते हैं वे फीडबैक चाप समुच्चय में शामिल करने के लिए बेकार हैं।[25] जब इन घटकों में से एक को दो शीर्षों को हटाकर दो डिस्कनेक्ट किए गए उपग्राफ में अलग किया जा सकता है, तो एक अधिक जटिल अपघटन लागू होता है, जिससे समस्या को इसके दृढ़ता से जुड़े घटकों के एसपीक्यूआर पेड़ से प्राप्त उप-समस्याओं में विभाजित किया जा सकता है।[26]

सटीक

न्यूनतम फीडबैक चाप समुच्चय को खोजने का एक तरीका शीर्षों के क्रम की खोज करना है, ताकि क्रम में यथासंभव कुछ किनारों को बाद के शीर्षों से पहले के शीर्षों की ओर दिष्ट किया जा सके।[27] एक के सभी क्रमपरिवर्तन खोज रहे हैं -vertex ग्राफ लगेगा time , लेकिन हेल्ड-कार्प एल्गोरिदम पर आधारित एक गतिशील प्रोग्रामिंग विधि इष्टतम क्रमपरिवर्तन पा सकती है time , स्थान की घातीय मात्रा का भी उपयोग कर रहा है।[28][29] एक फूट डालो और जीतो एल्गोरिथ्म जो शीर्षों के सभी विभाजनों को दो समान उपसमुच्चयों में परीक्षण करता है और प्रत्येक उपसमुच्चय के भीतर पुनरावृत्ति करता है, समस्या को हल कर सकता है time , बहुपद स्थान का उपयोग करना।[29]

पैरामीटरयुक्त जटिलता में, एल्गोरिदम के लिए समय को न केवल इनपुट ग्राफ़ के आकार के संदर्भ में मापा जाता है, बल्कि ग्राफ़ के एक अलग पैरामीटर के संदर्भ में भी मापा जाता है। विशेष रूप से, न्यूनतम फीडबैक चाप समुच्चय समस्या के लिए, तथाकथित प्राकृतिक पैरामीटर न्यूनतम फीडबैक चाप समुच्चय का आकार है। के साथ ग्राफ़ पर शिखर, प्राकृतिक के साथ parameter , फीडबैक चाप समुच्चय समस्या को हल किया जा सकता है time , इसे समतुल्य फीडबैक वर्टेक्स समुच्चय समस्या में परिवर्तित करके और एक पैरामीटरयुक्त फीडबैक वर्टेक्स समुच्चय एल्गोरिदम लागू करके। क्योंकि के प्रतिपादक इस एल्गोरिथ्म में है constant , स्वतंत्र of , इस एल्गोरिदम को फिक्स्ड-पैरामीटर ट्रैक्टेबल कहा जाता है।[30]

प्राकृतिक मापदण्ड के अतिरिक्त अन्य मापदण्डों का भी अध्ययन किया गया है। डायनेमिक प्रोग्रामिंग का उपयोग करके एक निश्चित-पैरामीटर ट्रैक्टेबल एल्गोरिदम न्यूनतम फीडबैक चाप समुच्चय पा सकता है time , कहाँ अंतर्निहित अप्रत्यक्ष ग्राफ़ का सर्किट रैंक है। सर्किट रैंक फीडबैक चाप समुच्चय का एक अप्रत्यक्ष एनालॉग है, किनारों की न्यूनतम संख्या जिसे ग्राफ़ से एक फैले हुए पेड़ तक कम करने के लिए हटाने की आवश्यकता होती है; न्यूनतम फीडबैक चाप समुच्चय की तुलना में इसकी गणना करना बहुत आसान है।[24] के ग्राफ़ के लिए treewidth , ग्राफ़ के पेड़ के अपघटन पर गतिशील प्रोग्रामिंग ग्राफ़ आकार और घातांक में समय बहुपद में निर्धारित न्यूनतम फीडबैक चाप पा सकती है in .घातांकीय समय परिकल्पना के अंतर्गत, इससे बेहतर कोई निर्भरता नहीं संभव है।[31]

फीडबैक चाप समुच्चय के आकार को कम करने के बजाय, शोधकर्ताओं ने किसी भी शीर्ष से हटाए गए किनारों की अधिकतम संख्या को कम करने पर भी ध्यान दिया है। समस्या की इस भिन्नता को रैखिक समय में हल किया जा सकता है।[32] सभी न्यूनतम फीडबैक चाप समुच्चय को प्रति समुच्चय बहुपद विलंब के साथ एक एल्गोरिदम द्वारा सूचीबद्ध किया जा सकता है।[33]

अनुमानित

Unsolved problem in mathematics:

Does the feedback arc set problem have an approximation algorithm with a constant approximation ratio?

(more unsolved problems in mathematics)

फीडबैक चाप समुच्चय के लिए सबसे प्रसिद्ध बहुपद-समय सन्निकटन एल्गोरिथ्म में गैर-स्थिर सन्निकटन अनुपात है . इसका मतलब यह है कि फीडबैक चाप समुच्चय का आकार जो इसे मिलता है वह अधिकतम इस कारक से इष्टतम से बड़ा है।[21] यह निर्धारित करना कि क्या फीडबैक चाप समुच्चय में एक स्थिर-अनुपात सन्निकटन एल्गोरिथ्म है, या क्या एक गैर-स्थिर अनुपात आवश्यक है, एक खुली समस्या बनी हुई है।[34]

अधिकतम अचक्रीयउपग्राफ समस्या में एक आसान सन्निकटन एल्गोरिथ्म है जो एक सन्निकटन अनुपात प्राप्त करता है of :

  • शीर्षों का मनमाना क्रम ठीक करें
  • किनारों को दो अचक्रीय उपसमूहों में विभाजित करें, एक में किनारे क्रम के अनुरूप दिष्ट होते हैं, और दूसरे में क्रम के विपरीत दिशा में दिष्ट किनारे होते हैं।
  • दो उपग्राफों में से बड़े को लौटाएँ।

ऑर्डर चुनने के लिए एक लालची एल्गोरिदम का उपयोग करके इसे बेहतर बनाया जा सकता है। यह एल्गोरिदम एक शीर्ष को ढूंढता है और हटा देता है जिसके आने वाले और बाहर जाने वाले किनारों की संख्या यथासंभव दूर होती है, शेष ग्राफ़ को पुनरावर्ती रूप से ऑर्डर करती है, और फिर हटाए गए शीर्ष को परिणामी क्रम के एक छोर पर रखती है। के साथ ग्राफ़ के लिए किनारों और शीर्षों पर, यह एक चक्रीय उपग्राफ उत्पन्न करता है किनारे, रैखिक समय में, एक सन्निकटन अनुपात देते हैं of .[35] एक और, अधिक जटिल, बहुपद समय सन्निकटन एल्गोरिदम अधिकतम वाले ग्राफ़ पर लागू होता है degree , और एक अचक्रीयउपग्राफ़ पाता है किनारों, का एक सन्निकटन अनुपात दे रहा है form .[36][37] कब , सन्निकटन अनुपात हासिल किया जा सकता है।[38]

प्रतिबंधित इनपुट

दिष्ट समतलीय ग्राफ़ में, फीडबैक चाप समुच्चय समस्या परिणामी ग्राफ़ को मजबूती दृढ़ता से जुड़ा हुआ ग्राफ़ बनाने के लिए किनारों के एक समुच्चय (एक डाइजॉइन) को अनुबंधित करने की समस्या का दोहरा ग्राफ़ है।[39] यह दोहरी समस्या बहुपद रूप से हल करने योग्य है,[40] और इसलिए समतल न्यूनतम फीडबैक चाप समुच्चय समस्या भी है।[41][40]इसमें समाधान किया जा सकता है time .[42] समस्या का एक भारित संस्करण हल किया जा सकता है time ,[39] या जब भार धनात्मक पूर्णांक होते हैं जो अधिकतम a होते हैं number , में time .[42] इन समतल एल्गोरिदम को उन ग्राफ़ों तक बढ़ाया जा सकता है जिनमें उपयोगिता ग्राफ़ नहीं है एक ग्राफ लघु के रूप में, इस तथ्य का उपयोग करते हुए कि इन ग्राफ़ के त्रिकोणीय घटक या तो समतल या परिबद्ध आकार के हैं।[26] प्लेनर ग्राफ़ को दिष्ट ग्राफ़ के एक वर्ग के लिए एक अलग तरीके से सामान्यीकृत किया गया है जिसे कमजोर अचक्रीयडिग्राफ कहा जाता है, जिसे एक निश्चित पॉलीहेड्रल कॉम्बिनेटरिक्स के अभिन्न पॉलीटोप द्वारा परिभाषित किया गया है। प्रत्येक तलीय दिष्ट ग्राफ इस अर्थ में कमजोर रूप से चक्रीय है, और फीडबैक चाप समुच्चय समस्या को सभी कमजोर चक्रीय डिग्राफ के लिए बहुपद समय में हल किया जा सकता है।[43]

नियंत्रण-प्रवाह ग्राफ#रिड्यूसिबिलिटी दिष्ट ग्राफ़ का एक अन्य वर्ग है जिस पर फीडबैक चाप समुच्चय समस्या को बहुपद समय में हल किया जा सकता है। ये ग्राफ़ कई प्रोग्रामिंग भाषाओं के लिए संरचित कार्यक्रमों में नियंत्रण के प्रवाह का वर्णन करते हैं। हालाँकि संरचित कार्यक्रम अक्सर समतल दिष्ट प्रवाह ग्राफ़ उत्पन्न करते हैं, रिड्यूसिबिलिटी की परिभाषा के लिए ग्राफ़ का समतल होना आवश्यक नहीं है।[44]

जब न्यूनतम फीडबैक चाप समुच्चय समस्या टूर्नामेंट (ग्राफ सिद्धांत) तक सीमित होती है, तो इसमें एक बहुपद-समय सन्निकटन योजना होती है, जो समस्या के भारित संस्करण को सामान्यीकृत करती है।[45] टूर्नामेंटों पर भारित फीडबैक चाप समुच्चय के लिए एक सबएक्सपोनेंशियल पैरामीटरयुक्त एल्गोरिदम भी जाना जाता है।[14] घने ग्राफ़ के लिए अधिकतम चक्रीय उपग्राफ़ समस्या में एक बहुपद-समय सन्निकटन योजना भी होती है। इसका मुख्य विचार समस्या के रैखिक प्रोग्रामिंग विश्राम के लिए यादृच्छिक राउंडिंग लागू करना है, और विस्तारक ग्राफ़ पर चलने का उपयोग करके परिणामी एल्गोरिदम को डीरैंडमाइज़ करना है।[34][46]

कठोरता

एनपी-कठोरता

एनपी-पूर्णता में कमी, बड़े पीले ग्राफ के शीर्ष कवर से लेकर छोटे नीले ग्राफ में न्यूनतम फीडबैक चाप समुच्चय तक, प्रत्येक पीले शीर्ष को दो आसन्न नीले ग्राफ कोने में विस्तारित करती है, और प्रत्येक अप्रत्यक्ष पीला किनारा दो विपरीत दिशा वाले किनारों में। न्यूनतम शीर्ष कवर (ऊपरी बाएँ और निचले दाएँ पीले कोने) लाल न्यूनतम फीडबैक चाप समुच्चय से मेल खाता है।

एनपी-पूर्णता के सिद्धांत को न्यूनतम फीडबैक चाप समुच्चय पर लागू करने के लिए, समस्या को एक अनुकूलन समस्या (सभी चक्रों को तोड़ने के लिए कुछ किनारों को कैसे हटाया जा सकता है) से समतुल्य निर्णय संस्करण में संशोधित करना आवश्यक है, हाँ के साथ या कोई उत्तर नहीं (क्या इसे हटाना संभव है किनारों)। इस प्रकार, फीडबैक चाप समुच्चय समस्या का निर्णय संस्करण एक दिष्ट ग्राफ और ए दोनों को इनपुट के रूप में लेता है number . यह पूछता है कि क्या सभी चक्रों को अधिक से अधिक हटाकर तोड़ा जा सकता है किनारों, या समकक्ष रूप से क्या कम से कम एक अचक्रीयउपग्राफ है किनारों. यह समस्या एनपी-पूर्ण है, जिसका अर्थ है कि न तो इसमें और न ही अनुकूलन समस्या में बहुपद समय एल्गोरिदम होने की उम्मीद है। यह रिचर्ड एम. कार्प के कार्प की 21 एनपी-पूर्ण समस्याओं के मूल समुच्चय में से एक था|21 एनपी-पूर्ण समस्याएं; इसकी एनपी-पूर्णता कार्प और यूजीन लॉलर द्वारा साबित की गई थी कि एक और कठिन समस्या, वर्टेक्स कवर समस्या के लिए इनपुट को फीडबैक चाप समुच्चय निर्णय समस्या के समकक्ष इनपुट में परिवर्तित (कम) किया जा सकता है।[47][48]

कुछ एनपी-पूर्ण समस्याएं तब आसान हो सकती हैं जब उनके इनपुट विशेष मामलों तक सीमित हों। लेकिन फीडबैक चाप समुच्चय समस्या के सबसे महत्वपूर्ण विशेष मामले, टूर्नामेंट के मामले में, समस्या एनपी-पूर्ण बनी हुई है।[49][50]

अप्राप्यता

जटिलता वर्ग APX को अनुकूलन समस्याओं से युक्त के रूप में परिभाषित किया गया है जिसमें एक बहुपद समय सन्निकटन एल्गोरिथ्म होता है जो एक स्थिर सन्निकटन अनुपात प्राप्त करता है। हालाँकि फीडबैक चाप समुच्चय समस्या के लिए ऐसे सन्निकटन ज्ञात नहीं हैं, समस्या को APX-हार्ड के रूप में जाना जाता है, जिसका अर्थ है कि इसके लिए सटीक सन्निकटन का उपयोग APX में अन्य सभी समस्याओं के लिए समान सटीक सन्निकटन प्राप्त करने के लिए किया जा सकता है। इसके कठोरता प्रमाण के परिणामस्वरूप, जब तक कि पी = एनपी न हो, इसका कोई बहुपद समय सन्निकटन अनुपात 1.3606 से बेहतर नहीं है। यह सन्निकटन की कठोरता के लिए वही सीमा है जो वर्टेक्स कवर के लिए जानी जाती है, और प्रमाण वर्टेक्स कवर से फीडबैक चाप समुच्चय तक कार्प-लॉलर कमी (जटिलता) का उपयोग करता है, जो सन्निकटन की गुणवत्ता को संरक्षित करता है।[34][51][52][53] एक अलग कमी से, अधिकतम अचक्रीयउपग्राफ समस्या भी एपीएक्स-हार्ड है, और एनपी-हार्ड को इष्टतम के 65/66 के कारक के भीतर अनुमानित किया जा सकता है।[38]

इन समस्याओं के सन्निकटन की कठोरता का अध्ययन अप्रमाणित कम्प्यूटेशनल कठोरता मान्यताओं के तहत भी किया गया है जो कम्प्यूटेशनल जटिलता सिद्धांत में मानक हैं लेकिन पी ≠ एनपी से अधिक मजबूत हैं। यदि अद्वितीय गेम का अनुमान सत्य है, तो न्यूनतम फीडबैक चाप समुच्चय समस्या को किसी भी स्थिर कारक के भीतर बहुपद समय में अनुमानित करना कठिन है, और अधिकतम फीडबैक चाप समुच्चय समस्या को एक कारक के भीतर अनुमानित करना कठिन है। of , के लिए every .[54] सन्निकटन एल्गोरिदम के लिए बहुपद समय से परे, यदि घातीय समय परिकल्पना सत्य है, तो प्रत्येक के लिए न्यूनतम फीडबैक चाप समुच्चय में किसी कारक के भीतर कोई सन्निकटन नहीं होता है जिसकी गणना उपघातीय समय सीमा में की जा सकती है .[55]

सिद्धांत

समतल दिष्ट ग्राफ़ में, फीडबैक चाप समुच्चय समस्या न्यूनतम-अधिकतम प्रमेय का पालन करती है: फीडबैक चाप समुच्चय का न्यूनतम आकार किनारे-असंगत दिष्ट चक्रों की अधिकतम संख्या के बराबर होता है जो ग्राफ़ में पाए जा सकते हैं।[41][56] यह कुछ अन्य ग्राफ़ के लिए सत्य नहीं है; उदाहरण के लिए पहला चित्रण गैर-प्लानर ग्राफ़ का एक दिष्ट संस्करण दिखाता है जिसमें फीडबैक चाप समुच्चय का न्यूनतम आकार दो है, जबकि किनारे-असंगत दिष्ट चक्रों की अधिकतम संख्या केवल एक है।

प्रत्येक टूर्नामेंट ग्राफ़ में एक हैमिल्टनियन पथ होता है, और हैमिल्टनियन पथ न्यूनतम फीडबैक चाप समुच्चय के साथ एक-के-लिए-एक के अनुरूप होते हैं, जो संबंधित पथ से अलग होते हैं। फीडबैक चाप समुच्चय के लिए हैमिल्टनियन पथ इसके चाप को उलट कर और परिणामी अचक्रीयटूर्नामेंट का टोपोलॉजिकल ऑर्डर ढूंढकर पाया जाता है। क्रम की प्रत्येक लगातार जोड़ी फीडबैक चाप समुच्चय से अलग होनी चाहिए, क्योंकि अन्यथा उस जोड़ी को उलट कर एक छोटा फीडबैक चाप समुच्चय मिल सकता है। इसलिए, यह क्रम सभी शीर्षों को कवर करते हुए, मूल टूर्नामेंट के चापों के माध्यम से एक पथ देता है। इसके विपरीत, किसी भी हैमिल्टनियन पथ से, किनारों का समुच्चय जो पथ में बाद के शीर्षों को पहले वाले शीर्षों से जोड़ता है, एक फीडबैक चाप समुच्चय बनाता है। यह न्यूनतम है, क्योंकि इसका प्रत्येक किनारा हैमिल्टनियन पथ किनारों वाले एक चक्र से संबंधित है जो ऐसे अन्य सभी चक्रों से अलग है।[57] एक टूर्नामेंट में, ऐसा हो सकता है कि न्यूनतम फीडबैक चाप समुच्चय और अधिकतम अचक्रीयउपग्राफ दोनों आधे किनारों के करीब हों। अधिक सटीक रूप से, प्रत्येक टूर्नामेंट ग्राफ़ में आकार का फीडबैक चाप समुच्चय होता है , और कुछ टूर्नामेंटों के लिए आकार की आवश्यकता होती है .[58] लगभग सभी टूर्नामेंटों के लिए, आकार कम से कम होता है .[59] प्रत्येक दिष्ट चक्रीय ग्राफ इसे एक बड़े टूर्नामेंट ग्राफ के उपग्राफ के रूप में इस तरह से एम्बेड किया जा सकता है टूर्नामेंट का अद्वितीय न्यूनतम फीडबैक चाप समुच्चय है। इस टूर्नामेंट के आकार को उलटी संख्या के रूप में परिभाषित किया गया है of , और शीर्षों की समान संख्या वाले दिष्ट चक्रीय ग्राफों में यह सबसे बड़ा है जब यह अपने आप में एक (एसाइक्लिक) टूर्नामेंट है।[60][61]

एक दिष्ट ग्राफ़ में एक यूलर टावर होता है जब भी यह दृढ़ता से जुड़ा होता है और प्रत्येक शीर्ष पर आने वाले और बाहर जाने वाले किनारों की समान संख्या होती है। ऐसे ग्राफ़ के लिए, साथ किनारों और शीर्षों पर, न्यूनतम फीडबैक चाप समुच्चय का आकार हमेशा कम से कम होता है . ऐसे अनगिनत यूलेरियन दिष्ट ग्राफ़ हैं जिनके लिए यह सीमा तंग है।[62] यदि एक दिष्ट ग्राफ है शीर्ष, प्रति शीर्ष अधिकतम तीन किनारों के साथ, तो इसमें अधिकतम फीडबैक चाप समुच्चय होता है किनारों, और कुछ ग्राफ़ के लिए इतने की आवश्यकता होती है। यदि एक दिष्ट ग्राफ है किनारों, प्रति शीर्ष अधिकतम चार किनारों के साथ, तो इसमें अधिकतम फीडबैक चाप समुच्चय होता है किनारों, और कुछ ग्राफ़ के लिए इतने की आवश्यकता होती है।[63]

संदर्भ

  1. ↑ "Main draw – Men", Rio 2016, Fédération Internationale de Volleyball, archived from the original on 2016-12-23, retrieved 2021-11-14
  2. ↑ 2.0 2.1 2.2 Hubert, Lawrence (1976), "Seriation using asymmetric proximity measures", British Journal of Mathematical and Statistical Psychology, 29 (1): 32–52, doi:10.1111/j.2044-8317.1976.tb00701.x, MR 0429180
  3. ↑ 3.0 3.1 3.2 Remage, Russell Jr.; Thompson, W. A. Jr. (1966), "Maximum-likelihood paired comparison rankings", Biometrika, 53 (1–2): 143–149, doi:10.1093/biomet/53.1-2.143, JSTOR 2334060, MR 0196854, PMID 5964054
  4. ↑ Goddard, Stephen T. (1983), "Ranking in tournaments and group decisionmaking", Management Science, 29 (12): 1384–1392, doi:10.1287/mnsc.29.12.1384, MR 0809110; note that the algorithm suggested by Goddard for finding minimum-violation rankings is incorrect
  5. ↑ Vaziri, Baback; Dabadghao, Shaunak; Yih, Yuehwern; Morin, Thomas L. (January 2018), "Properties of sports ranking methods" (PDF), Journal of the Operational Research Society, 69 (5): 776–787, doi:10.1057/s41274-017-0266-8, S2CID 51887586
  6. ↑ Coppersmith, Don; Fleischer, Lisa K.; Rurda, Atri (2010), "Ordering by weighted number of wins gives a good ranking for weighted tournaments", ACM Transactions on Algorithms, 6 (3): A55:1–A55:13, doi:10.1145/1798596.1798608, MR 2682624, S2CID 18416
  7. ↑ Seyfarth, Robert M. (November 1976), "Social relationships among adult female baboons", Animal Behaviour, 24 (4): 917–938, doi:10.1016/s0003-3472(76)80022-x, S2CID 54284406
  8. ↑ Estep, D.Q.; Crowell-Davis, S.L.; Earl-Costello, S.-A.; Beatey, S.A. (January 1993), "Changes in the social behaviour of drafthorse (Equus caballus) mares coincident with foaling", Applied Animal Behaviour Science, 35 (3): 199–213, doi:10.1016/0168-1591(93)90137-e
  9. ↑ Eickwort, George C. (April 2019), "Dominance in a cockroach (Nauphoeta)", Insect Behavior, CRC Press, pp. 120–126, doi:10.1201/9780429049262-18, S2CID 203898549
  10. ↑ Slater, Patrick (1961), "Inconsistencies in a schedule of paired comparisons", Biometrika, 48 (3–4): 303–312, doi:10.1093/biomet/48.3-4.303, JSTOR 2332752
  11. ↑ Brunk, H. D. (1960), "Mathematical models for ranking from paired comparisons", Journal of the American Statistical Association, 55 (291): 503–520, doi:10.2307/2281911, hdl:2027/mdp.39015095254010, JSTOR 2281911, MR 0115242
  12. ↑ Thompson, W. A., Jr.; Remage, Russell, Jr. (1964), "Rankings from paired comparisons", Annals of Mathematical Statistics, 35 (2): 739–747, doi:10.1214/aoms/1177703572, JSTOR 2238526, MR 0161419{{citation}}: CS1 maint: multiple names: authors list (link)
  13. ↑ Kemeny, John G. (Fall 1959), "Mathematics without numbers", Daedalus, 88 (4): 577–591, JSTOR 20026529
  14. ↑ 14.0 14.1 Karpinski, Marek; Schudy, Warren (2010), "Faster algorithms for feedback arc set tournament, Kemeny rank aggregation and betweenness tournament", in Cheong, Otfried; Chwa, Kyung-Yong; Park, Kunsoo (eds.), Algorithms and Computation - 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part I, Lecture Notes in Computer Science, vol. 6506, Springer, pp. 3–14, arXiv:1006.4396, doi:10.1007/978-3-642-17517-6_3, S2CID 16512997
  15. ↑ 15.0 15.1 Unger, Stephen H. (April 26, 1957), A study of asynchronous logical feedback networks, Technical reports, vol. 320, Massachusetts Institute of Technology, Research Laboratory of Electronics, hdl:1721.1/4763
  16. ↑ Feehrer, John R.; Jordan, Harry F. (December 1995), "Placement of clock gates in time-of-flight optoelectronic circuits", Applied Optics, 34 (35): 8125–8136, Bibcode:1995ApOpt..34.8125F, doi:10.1364/ao.34.008125, PMID 21068927
  17. ↑ Rosen, Edward M.; Henley, Ernest J. (Summer 1968), "The New Stoichiometry", Chemical Engineering Education, 2 (3): 120–125, archived from the original on 2021-08-02, retrieved 2021-08-02
  18. ↑ Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1998), "Layered Drawings of Digraphs", Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, pp. 265–302, ISBN 9780133016154
  19. ↑ Bastert, Oliver; Matuszewski, Christian (2001), "Layered drawings of digraphs", in Kaufmann, Michael; Wagner, Dorothea (eds.), Drawing Graphs: Methods and Models, Lecture Notes in Computer Science, vol. 2025, Springer-Verlag, pp. 87–120, doi:10.1007/3-540-44969-8_5
  20. ↑ Demetrescu, Camil; Finocchi, Irene (2001), "Break the "right" cycles and get the "best" drawing", ACM Journal of Experimental Algorithmics, 6: 171–182, MR 2027115
  21. ↑ 21.0 21.1 21.2 Even, G.; Naor, J.; Schieber, B.; Sudan, M. (1998), "Approximating minimum feedback sets and multicuts in directed graphs", Algorithmica, 20 (2): 151–174, doi:10.1007/PL00009191, MR 1484534, S2CID 2437790
  22. ↑ 22.0 22.1 Minoura, Toshimi (1982), "Deadlock avoidance revisited", Journal of the ACM, 29 (4): 1023–1048, doi:10.1145/322344.322351, MR 0674256, S2CID 5284738
  23. ↑ Mishra, Sounaka; Sikdar, Kripasindhu (2004), "On approximability of linear ordering and related NP-optimization problems on graphs", Discrete Applied Mathematics, 136 (2–3): 249–269, doi:10.1016/S0166-218X(03)00444-X, MR 2045215
  24. ↑ 24.0 24.1 Hecht, Michael (2017), "Exact localisations of feedback sets", Theory of Computing Systems, 62 (5): 1048–1084, arXiv:1702.07612, doi:10.1007/s00224-017-9777-6, S2CID 18394348
  25. ↑ Park, S.; Akers, S.B. (1992), "An efficient method for finding a minimal feedback arc set in directed graphs", Proceedings of the 1992 IEEE International Symposium on Circuits and Systems (ISCAS '92), vol. 4, pp. 1863–1866, doi:10.1109/iscas.1992.230449, S2CID 122603659
  26. ↑ 26.0 26.1 Nutov, Zeev; Penn, Michal (2000), "On integrality, stability and composition of dicycle packings and covers", Journal of Combinatorial Optimization, 4 (2): 235–251, doi:10.1023/A:1009802905533, MR 1772828, S2CID 207632524
  27. ↑ Younger, D. (1963), "Minimum feedback arc sets for a directed graph", IEEE Transactions on Circuit Theory, 10 (2): 238–245, doi:10.1109/tct.1963.1082116
  28. ↑ Lawler, E. (1964), "A comment on minimum feedback arc sets", IEEE Transactions on Circuit Theory, 11 (2): 296–297, doi:10.1109/tct.1964.1082291
  29. ↑ 29.0 29.1 Bodlaender, Hans L.; Fomin, Fedor V.; Koster, Arie M. C. A.; Kratsch, Dieter; Thilikos, Dimitrios M. (2012), "A note on exact algorithms for vertex ordering problems on graphs", Theory of Computing Systems, 50 (3): 420–432, doi:10.1007/s00224-011-9312-0, hdl:1956/4556, MR 2885638, S2CID 9967521
  30. ↑ Chen, Jianer; Liu, Yang; Lu, Songjian; O'Sullivan, Barry; Razgon, Igor (2008), "A fixed-parameter algorithm for the directed feedback vertex set problem", Journal of the ACM, 55 (5): 1–19, doi:10.1145/1411509.1411511, S2CID 1547510
  31. ↑ Bonamy, Marthe; Kowalik, Lukasz; Nederlof, Jesper; Pilipczuk, Michal; Socala, Arkadiusz; Wrochna, Marcin (2018), "On directed feedback vertex set parameterized by treewidth", in Brandstädt, Andreas; Köhler, Ekkehard; Meer, Klaus (eds.), Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Cottbus, Germany, June 27-29, 2018, Proceedings, Lecture Notes in Computer Science, vol. 11159, Springer, pp. 65–78, arXiv:1707.01470, doi:10.1007/978-3-030-00256-5_6, S2CID 8008855
  32. ↑ Lin, Lishin; Sahni, Sartaj (1989), "Fair edge deletion problems", IEEE Transactions on Computers, 38 (5): 756–761, doi:10.1109/12.24280, MR 0994519
  33. ↑ Schwikowski, Benno; Speckenmeyer, Ewald (2002), "On enumerating all minimal solutions of feedback problems", Discrete Applied Mathematics, 117 (1–3): 253–265, doi:10.1016/S0166-218X(00)00339-5, MR 1881280
  34. ↑ 34.0 34.1 34.2 Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek; Woeginger, Gerhard (2000), "Minimum Feedback Arc Set", A compendium of NP optimization problems, archived from the original on 2021-07-29, retrieved 2021-07-29
  35. ↑ Eades, Peter; Lin, Xuemin; Smyth, W. F. (1993), "A fast and effective heuristic for the feedback arc set problem", Information Processing Letters, 47 (6): 319–323, doi:10.1016/0020-0190(93)90079-O, MR 1256786, archived from the original on 2020-10-22, retrieved 2021-08-01
  36. ↑ Berger, Bonnie; Shor, Peter W. (1997), "Tight bounds for the maximum acyclic subgraph problem", Journal of Algorithms, 25 (1): 1–18, doi:10.1006/jagm.1997.0864, MR 1474592
  37. ↑ Hassin, Refael; Rubinstein, Shlomi (1994), "Approximations for the maximum acyclic subgraph problem", Information Processing Letters, 51 (3): 133–140, doi:10.1016/0020-0190(94)00086-7, MR 1290207
  38. ↑ 38.0 38.1 Newman, Alantha (June 2000), Approximating the maximum acyclic subgraph (Master’s thesis), Massachusetts Institute of Technology, hdl:1721.1/86548, as cited by Guruswami et al. (2011)
  39. ↑ 39.0 39.1 Gabow, Harold N. (1995), "Centroids, representations, and submodular flows", Journal of Algorithms, 18 (3): 586–628, doi:10.1006/jagm.1995.1022, MR 1334365
  40. ↑ 40.0 40.1 Frank, András (1981), "How to make a digraph strongly connected", Combinatorica, 1 (2): 145–153, doi:10.1007/BF02579270, MR 0625547, S2CID 27825518
  41. ↑ 41.0 41.1 Lucchesi, C. L.; Younger, D. H. (1978), "A minimax theorem for directed graphs", Journal of the London Mathematical Society, Second Series, 17 (3): 369–374, doi:10.1112/jlms/s2-17.3.369, MR 0500618
  42. ↑ 42.0 42.1 Gabow, Harold N. (1993), "A framework for cost-scaling algorithms for submodular flow problems", 34th Annual Symposium on Foundations of Computer Science, Palo Alto, California, USA, 3-5 November 1993, IEEE Computer Society, pp. 449–458, doi:10.1109/SFCS.1993.366842, MR 1328441, S2CID 32162097
  43. ↑ Grötschel, Martin; Jünger, Michael; Reinelt, Gerhard (1985), "On the acyclic subgraph polytope", Mathematical Programming, 33 (1): 28–42, doi:10.1007/BF01582009, MR 0809747, S2CID 206798683
  44. ↑ Ramachandran, Vijaya (1988), "Finding a minimum feedback arc set in reducible flow graphs", Journal of Algorithms, 9 (3): 299–313, doi:10.1016/0196-6774(88)90022-3, MR 0955140
  45. ↑ Kenyon-Mathieu, Claire; Schudy, Warren (2007), "How to rank with few errors: a PTAS for weighted feedback arc set on tournaments", in Johnson, David S.; Feige, Uriel (eds.), Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pp. 95–103, doi:10.1145/1250790.1250806, S2CID 9436948, ECCC TR06-144; see also author's extended version Archived 2009-01-15 at the Wayback Machine
  46. ↑ Arora, Sanjeev; Frieze, Alan; Kaplan, Haim (2002), "A new rounding procedure for the assignment problem with applications to dense graph arrangement problems", Mathematical Programming, 92 (1): 1–36, doi:10.1007/s101070100271, MR 1892295, S2CID 3207086, archived from the original on 2021-08-03, retrieved 2021-08-03
  47. ↑ Karp, Richard M. (1972), "Reducibility among combinatorial problems", Complexity of Computer Computations, Proc. Sympos. IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., New York: Plenum, pp. 85–103
  48. ↑ Garey, Michael R.; Johnson, David S. (1979), "A1.1: GT8", Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, p. 192, ISBN 0-7167-1045-5
  49. ↑ Alon, Noga (2006), "Ranking tournaments", SIAM Journal on Discrete Mathematics, 20 (1): 137–142, doi:10.1137/050623905, MR 2257251
  50. ↑ Charbit, Pierre; Thomassé, Stéphan; Yeo, Anders (2007), "The minimum feedback arc set problem is NP-hard for tournaments" (PDF), Combinatorics, Probability and Computing, 16 (1): 1–4, doi:10.1017/S0963548306007887, MR 2282830, S2CID 36539840
  51. ↑ Ausiello, G.; D'Atri, A.; Protasi, M. (1980), "Structure preserving reductions among convex optimization problems", Journal of Computer and System Sciences, 21 (1): 136–153, doi:10.1016/0022-0000(80)90046-X, MR 0589808
  52. ↑ Kann, Viggo (1992), On the Approximability of NP-complete Optimization Problems (PDF) (Ph.D. thesis), Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm, archived (PDF) from the original on 2010-12-29, retrieved 2007-10-11
  53. ↑ Dinur, Irit; Safra, Samuel (2005), "On the hardness of approximating minimum vertex cover" (PDF), Annals of Mathematics, 162 (1): 439–485, doi:10.4007/annals.2005.162.439, archived (PDF) from the original on 2009-09-20, retrieved 2021-07-29; preliminary version in Dinur, Irit; Safra, Samuel (2002), "The importance of being biased", in Reif, John H. (ed.), Proceedings of the 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pp. 33–42, doi:10.1145/509907.509915, S2CID 1235048
  54. ↑ Guruswami, Venkatesan; Håstad, Johan; Manokaran, Rajsekar; Raghavendra, Prasad; Charikar, Moses (2011), "Beating the random ordering is hard: every ordering CSP is approximation resistant" (PDF), SIAM Journal on Computing, 40 (3): 878–914, doi:10.1137/090756144, MR 2823511, archived (PDF) from the original on 2021-07-31, retrieved 2021-07-31
  55. ↑ Bonnet, Édouard; Paschos, Vangelis Th. (2018), "Sparsification and subexponential approximation", Acta Informatica, 55 (1): 1–15, doi:10.1007/s00236-016-0281-2, MR 3757549, S2CID 3136275
  56. ↑ Lovász, László (1976), "On two minimax theorems in graph", Journal of Combinatorial Theory, Series B, 21 (2): 96–103, doi:10.1016/0095-8956(76)90049-6, MR 0427138
  57. ↑ Bar-Noy, Amotz; Naor, Joseph (1990), "Sorting, minimal feedback sets, and Hamilton paths in tournaments", SIAM Journal on Discrete Mathematics, 3 (1): 7–20, doi:10.1137/0403002, MR 1033709
  58. ↑ Spencer, J. (1980), "Optimally ranking unrankable tournaments", Periodica Mathematica Hungarica, 11 (2): 131–144, doi:10.1007/BF02017965, MR 0573525, S2CID 119894999
  59. ↑ Fernandez de la Vega, W. (1983), "On the maximum cardinality of a consistent set of arcs in a random tournament", Journal of Combinatorial Theory, Series B, 35 (3): 328–332, doi:10.1016/0095-8956(83)90060-6, MR 0735201
  60. ↑ Barthélémy, Jean-Pierre; Hudry, Olivier; Isaak, Garth; Roberts, Fred S.; Tesman, Barry (1995), "The reversing number of a digraph", Discrete Applied Mathematics, 60 (1–3): 39–76, doi:10.1016/0166-218X(94)00042-C, MR 1339075
  61. ↑ Isaak, Garth; Narayan, Darren A. (2004), "A classification of tournaments having an acyclic tournament as a minimum feedback arc set", Information Processing Letters, 92 (3): 107–111, doi:10.1016/j.ipl.2004.07.001, MR 2095357
  62. ↑ Huang, Hao; Ma, Jie; Shapira, Asaf; Sudakov, Benny; Yuster, Raphael (2013), "Large feedback arc sets, high minimum degree subgraphs, and long cycles in Eulerian digraphs", Combinatorics, Probability and Computing, 22 (6): 859–873, arXiv:1202.2602, doi:10.1017/S0963548313000394, hdl:20.500.11850/73894, MR 3111546, S2CID 7967738
  63. ↑ Hanauer, Kathrin; Brandenburg, Franz-Josef; Auer, Christopher (2013), "Tight upper bounds for minimum feedback arc sets of regular graphs", in Brandstädt, Andreas; Jansen, Klaus; Reischuk, Rüdiger (eds.), Graph-Theoretic Concepts in Computer Science - 39th International Workshop, WG 2013, Lübeck, Germany, June 19-21, 2013, Revised Papers, Lecture Notes in Computer Science, vol. 8165, Springer, pp. 298–309, doi:10.1007/978-3-642-45043-3_26, MR 3139198
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=फीडबैक_आर्क_सेट&oldid=219597’