1
我期待提出一個多項式時間算法，該算法以圖形G和整數K的形式輸入並確定G是否爲K-頂點連接。我在想這可能會利用深度優先搜索。我可以看到它如何不是一個無多項式的解決方案，即只刪除K個隨機頂點，運行DFS檢查連通性，然後再用一組不同的頂點組合。 〜O（n^K）的運行時間稍微多一些，並且顯然可以將其降低到多項式時間。任何想法我在這裏失蹤？我想它與運行DFS後得到的非樹頂點有關，但我不完全確定我在找什麼？提前致謝！確定一個圖是否是K-頂點連接的
編輯：爲了清楚，我是而不是尋找確定圖的連接性。相反，一個數字k在輸入時給出，我正在檢查圖形是否連通。它將而不是產生一個答案，給出了圖的連通性，只是一個是或否。
最快算法來確定的曲線的頂點的連接是由於Henzinger，饒，和Gabow（Computing Vertex Connectivity：Computing Vertex Connectivity：New Bounds from Old Techniques）並且在時間O（min {k^3 + n，kn} m）中運行，其中n是頂點的數量，m是邊緣的數量，並且k是連通性。這是一條評論，不是一個答案，因爲這篇文章背後是付費牆，我不想總結。 – oldboy 2012-04-11 23:39:30
啊，是的，如果上面沒有清楚的說明，我不會確定輸入圖的頂點連通性（我知道這在多項式時間內是不可行的），而只是爲了檢查圖是否爲k -連接的。所以我會得到一個圖形，比如說數字4，然後檢查圖形是否連接了4。這有意義嗎？ – user1257768 2012-04-12 13:07:28