2013-02-27 5 views
6

में डिग्री के स्थानीय ब्र्रिज ग्राफ में स्थानीयब्रिज (के) खोजने के लिए सबसे अच्छा एल्गोरिदम क्या होगा? डिग्री के स्थानीय पुल एक किनारे हैं जिनकी हटाने से कम से कम के लिए अपने दो अंत बिंदुओं के बीच सबसे छोटी दूरी बढ़ जाएगी।ग्राफ

विकिपीडिया: http://en.wikipedia.org/wiki/Bridge_(interpersonal)#Local_bridge

+0

क्या [फ़्लॉइड-वारशॉल एल्गोरिदम] (http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm) पर्याप्त है? – anatolyg

+2

क्या आप ग्राफ में सभी स्थानीय पुलों को खोजने में रुचि रखते हैं? शायद आपके मन में एक (या दो) विशिष्ट नोड्स थे। – phs

उत्तर

2

भागो एक सब कम से कम-पथ-लागत एल्गोरिथ्म, फ्लोयड-Warshall एल्गोरिथ्म की तरह है, लेकिन जहां ठेठ वास्तविक संख्या d के बजाय, दूरी के लिए tuples (d1,d2) का उपयोग करें:

  • d1 कम से कम पथ
  • d2 की लंबाई की लंबाई है दूसरा कम से कम पथ

फ्लोयड-Warshall एल्गोरिथ्म के लिए इस संशोधन आसान होना चाहिए।

जब आप सभी कम से कम-पथ-लागत एल्गोरिथ्म चल किया जाता है, localbridge(k) किनारों उन किनारों हैं e = {u, v} ऐसी है कि दूरी (1,d2)u और v संतुष्ट d2 >= k के बीच।