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