एक पूर्ण ग्राफ में सबसे बड़ी चक्की के आकार को खोजने के लिए एक तेज़ एल्गोरिदम (जिसमें कम से कम 1 तार वाले अजीब चक्र होते हैं) लगभग 100 शिखर के साथ ??सही ग्राफ में अधिकतम क्लिक्स ढूंढना
और ब्रूट फोर्स की तुलना में कोई आसान तरीका है क्योंकि यह एक आदर्श ग्राफ है और इसके लिए बहुपद समय समाधान होना चाहिए। लेकिन मैं एल्गोरिदम नहीं ढूंढ पा रहा हूं।
क्या लालची रंग सभी सही ग्राफों में इष्टतम रंग देता है ??
पृष्ठ 2 9 6 देखें, कुछ कामों के साथ आपको इस समस्या को हल करने के लिए सही रैखिक प्रोग्रामिंग बाधा लिखनी चाहिए।
http://www.scribd.com/doc/5710463/Geometric-Algorithms-And-Combinatorial-Optimization
+1: केवल उत्तर दें जो सही ग्राफ को संबोधित करता है, जिसके लिए क्लासिक समस्या पी –
100 कोने? Pffft। Cliquer के साथ कुछ सेकंड (शायद एक सेकंड का अंश) में बल दें। http://users.tkk.fi/pat/cliquer.html
में है, क्या आप एल्गोरिदम (मैंने प्रलेखन देखा है) समझा सकते हैं लेकिन सरल शब्दों में – copperhead
निश्चित रूप से। पहला क्लिकर शिखर के क्रमपरिवर्तन को परिभाषित करता है। मुझे लगता है कि डिफ़ॉल्ट रूप से यह इनपुट में आपके द्वारा उपयोग किए जाने वाले क्रम में होता है। दूसरा, क्लिकर सेट में सबसे बड़ा क्लिक ढूंढता है [i .... n], i = n-1 से i = 1 तक। जिस तरह से यह अब तक की सबसे बड़ी चक्की को याद करता है और जब नई क्लिक्स के लिए परीक्षण किया जाता है तो यह खोज को उजागर करता है जब यह स्पष्ट हो जाता है कि पहले गणना की गई क्लाइक आकारों से खोज के उस पथ के लिए एक बड़ा चक्कर पैदा करना असंभव होगा। –
क्या आपने कोई प्रयास किया है? –
मैंने कुछ दृष्टिकोणों का प्रयास किया लेकिन उनमें से सभी बहुत धीमी थीं। – copperhead
बस विकिपीडिया में यह पाया: सभी सही रेखांकन में , ग्राफ रंग समस्या, अधिकतम गुट समस्या है, और अधिकतम स्वतंत्र सेट समस्या सभी बहुपद समय में हल किया जा सकता (Grötschel, Lovasz और Schrijver 1988) Grötschel, मार्टिन; Lovász, László; श्रिजवर, अलेक्जेंडर (1 9 88)। ज्यामितीय एल्गोरिदम और कॉम्बिनेटोरियल अनुकूलन। स्प्रिंगर-वर्लग। विशेष रूप से अध्याय 9, "ग्राफिक्स में स्थिर सेट" देखें, पीपी 273-303। – yogsototh