2007年2月
Computing a minimum cut in a graph with dynamic edges incident to a designated vertex
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS
- 巻
- E90D
- 号
- 2
- 開始ページ
- 428
- 終了ページ
- 431
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1093/ietisy/e90-d.2.428
- 出版者・発行元
- IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG
We consider an edge-weighted graph G with a designated vertex v(0) such that weights of edges incident to v(0) may increase or decrease. We show that, with an O(mn + n(2) log n) time preprocessing, a minimum cut of the current G can be computed in O(log n) time per update of weight of any edge (v(0), u).
- リンク情報
- ID情報
-
- DOI : 10.1093/ietisy/e90-d.2.428
- ISSN : 0916-8532
- J-Global ID : 200902284484277990
- Web of Science ID : WOS:000244546400006