2005年1月
On 2-approximation to the vertex-connectivity in graphs
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS
- 巻
- E88D
- 号
- 1
- 開始ページ
- 12
- 終了ページ
- 16
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1093/ietisy/E88-D.1.12
- 出版者・発行元
- IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG
Given a graph G, we give a fast algorithm for approximating the vertex connectivity kappa of G. Our algorithm delivers a minimum vertex cut of G if kappa less than or equal to [delta/2], and returns a message "kappa > [delta/2]" otherwise, where delta denotes the minimum degree of G. The algorithm runs in O(n(2)(1 + min{kappa(2), kappa rootn}/delta)) time and O(n + m) space, where n and m denote the numbers of vertices and edges in G, respectively.
- リンク情報
-
- DOI
- https://doi.org/10.1093/ietisy/E88-D.1.12
- DBLP
- https://dblp.uni-trier.de/rec/journals/ieicet/Nagamochi05
- Web of Science
- https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000226443200003&DestApp=WOS_CPL
- URL
- http://search.ieice.org/bin/summary.php?id=e88-d_1_12&category=D&year=2005&lang=E&abst=
- URL
- http://dblp.uni-trier.de/db/journals/ieicet/ieicet88d.html#journals/ieicet/Nagamochi05
- ID情報
-
- DOI : 10.1093/ietisy/E88-D.1.12
- ISSN : 1745-1361
- DBLP ID : journals/ieicet/Nagamochi05
- Web of Science ID : WOS:000226443200003