On 2-Approximation to the Vertex-Connectivity in Graphs(<Special Section>Foundations of Computer Science)

スポンサーリンク

概要

• 論文の詳細を見る

• Given a graph G, we give a fast algorithm for approximating the vertex connectivity k of G. Our algorithm delivers a minimum vertex cut of G if k ≦ ⌊δ/2⌋, and returns a message "k > ⌊δ/2⌋" otherwise, where δ denotes the minimum degree of G. The algorithm runs in O (n^2 (1 + min{k^2, k √<n>} /δ) time and O (n + m) space, where n and m denote the numbers of vertices and edges in G, respectively.

• 社団法人電子情報通信学会の論文
• 2005-01-01

著者

• Nagamochi Hiroshi

  The Department Of Applied Mathematics And Physics Graduate School Of Informatics Kyoto University

• Nagamochi Hiroshi

  The Department Of Applied Mathematics And Physics Kyoto University

関連論文

• Increasing the Edge-Connectivity by Contracting a Vertex Subset in Graphs(Graph Algorithm, Foundations of Computer Science)
• On 2-Approximation to the Vertex-Connectivity in Graphs(Foundations of Computer Science)
• Kernel Methods for Chemical Compounds: From Classification to Design
• Better Approximation Algorithms for Grasp-and-Delivery Robot Routing Problems

スポンサーリンク