9
मैं एक डेटा संरचना की तलाश में हूं जो किसी भी डीएजी को स्टोर करेगा, लेकिन कुशलता से (यानी, किनारों/चरमों की संख्या में उप-रैखिक रूप से) पता लगा सकता है कि किनारे जोड़ने से चक्र बन जाएगा (और इस प्रकार आपको तोड़ने से रोकता है विश्वकोश invariant)। क्या किसी को ऐसी चीज पता है?क्या डीएजी के लिए कोई डेटा संरचना है जो कुशल संपादन का समर्थन करती है?
धन्यवाद!
यह पेपर, [बढ़ती टोपोलॉजिकल ऑर्डरिंग के लिए तेज़ एल्गोरिदम] (http://www.cs.princeton.edu/~sssix/papers/dto-conf.pdf), ** ** ** ** (एम) का दावा करता है^1/2) प्रति आर्क अतिरिक्त। सुनिश्चित नहीं है कि यह काफी अच्छा है, या यदि सबसे खराब स्थिति बाध्य है। मैंने परिचय से परे नहीं पढ़ा है। – Crosbie