Computing a Minimum Cut in a Graph with Dynamic Edges Incident to a Designated Vertex

Hiroshi NAGAMOCHI

doi:10.1093/ietisy/e90-d.2.428

Copy

Hiroshi NAGAMOCHI, "Computing a Minimum Cut in a Graph with Dynamic Edges Incident to a Designated Vertex" in IEICE TRANSACTIONS on Information, vol. E90-D, no. 2, pp. 428-431, February 2007, doi: 10.1093/ietisy/e90-d.2.428.
Abstract: We consider an edge-weighted graph G with a designated vertex v₀ such that weights of edges incident to v₀ may increase or decrease. We show that, with an O(mn+n²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₀,u}.
URL: https://globals.ieice.org/en_transactions/information/10.1093/ietisy/e90-d.2.428/_p

Copy

@ARTICLE{e90-d_2_428,
author={Hiroshi NAGAMOCHI, },
journal={IEICE TRANSACTIONS on Information},
title={Computing a Minimum Cut in a Graph with Dynamic Edges Incident to a Designated Vertex},
year={2007},
volume={E90-D},
number={2},
pages={428-431},
abstract={We consider an edge-weighted graph G with a designated vertex v₀ such that weights of edges incident to v₀ may increase or decrease. We show that, with an O(mn+n²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₀,u}.},
keywords={},
doi={10.1093/ietisy/e90-d.2.428},
ISSN={1745-1361},
month={February},}

Copy

TY - JOUR
TI - Computing a Minimum Cut in a Graph with Dynamic Edges Incident to a Designated Vertex
T2 - IEICE TRANSACTIONS on Information
SP - 428
EP - 431
AU - Hiroshi NAGAMOCHI
PY - 2007
DO - 10.1093/ietisy/e90-d.2.428
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E90-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2007
AB - We consider an edge-weighted graph G with a designated vertex v₀ such that weights of edges incident to v₀ may increase or decrease. We show that, with an O(mn+n²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₀,u}.
ER -