में डिग्री के स्थानीय ब्र्रिज ग्राफ में स्थानीयब्रिज (के) खोजने के लिए सबसे अच्छा एल्गोरिदम क्या होगा? डिग्री के स्थानीय पुल एक किनारे हैं जिनकी हटाने से कम से कम के लिए अपने दो अंत बिंदुओं के बीच सबसे छोटी दूरी बढ़ जाएगी।ग्राफ
विकिपीडिया: http://en.wikipedia.org/wiki/Bridge_(interpersonal)#Local_bridge
भागो एक सब कम से कम-पथ-लागत एल्गोरिथ्म, फ्लोयड-Warshall एल्गोरिथ्म की तरह है, लेकिन जहां ठेठ वास्तविक संख्या d के बजाय, दूरी के लिए tuples (d1,d2) का उपयोग करें:
d1 कम से कम पथd2 की लंबाई की लंबाई है दूसरा कम से कम पथफ्लोयड-Warshall एल्गोरिथ्म के लिए इस संशोधन आसान होना चाहिए।
जब आप सभी कम से कम-पथ-लागत एल्गोरिथ्म चल किया जाता है, localbridge(k) किनारों उन किनारों हैं e = {u, v} ऐसी है कि दूरी (1,d2)u और v संतुष्ट d2 >= k के बीच।
क्या [फ़्लॉइड-वारशॉल एल्गोरिदम] (http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm) पर्याप्त है? – anatolyg
क्या आप ग्राफ में सभी स्थानीय पुलों को खोजने में रुचि रखते हैं? शायद आपके मन में एक (या दो) विशिष्ट नोड्स थे। – phs