अधिकतम औसत डिग्री के साथ उपग्राफ ढूँढना। जटिलता?

Question

क्या सबसे बड़ी औसत डिग्री (जो स्वयं ग्राफ हो सकता है) के साथ उपग्राफ खोजने के लिए एक कुशल एल्गोरिदम है?

Answer 1

The paper "Finding a Maximum-Density Subgraph" by Andrew Goldberg ऐसे ग्राफ की पहचान करने के लिए बहुपद-समय एल्गोरिदम प्रदान करता है। ऐसा लगता है कि एल्गोरिदम उचित रूप से निर्मित ग्राफ पर अधिकतम प्रवाह एल्गोरिदम के लिए लॉगरिदमिक रूप से कई कॉल करता है। मैंने जो पढ़ा है, उससे ऐसा लगता है कि एल्गोरिदम औसत डिग्री पर केवल एक द्विआधारी खोज है जहां प्रत्येक अनुमान को मानक ग्राफ निर्माण पर अधिकतम प्रवाह का उपयोग करके चेक किया जाता है। अधिकांश जटिलता बहस में प्रतीत होती है कि निर्माण सही क्यों है।

आशा है कि इससे मदद मिलती है!