IEICE TRANSACTIONS on Information
Computing a Minimum Cut in a Graph with Dynamic Edges Incident to a Designated Vertex
Summary :
We consider an edge-weighted graph G with a designated vertex v0 such that weights of edges incident to v0 may increase or decrease. We show that, with an O(mn+n2log 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 {v0,u}.
- Publication
- IEICE TRANSACTIONS on Information Vol.E90-D No.2 pp.428-431
- Publication Date
- 2007/02/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1093/ietisy/e90-d.2.428
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science)
- Category
- Graph Algorithms
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
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 v0 such that weights of edges incident to v0 may increase or decrease. We show that, with an O(mn+n2log 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 {v0,u}.
URL: https://global.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 v0 such that weights of edges incident to v0 may increase or decrease. We show that, with an O(mn+n2log 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 {v0,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 v0 such that weights of edges incident to v0 may increase or decrease. We show that, with an O(mn+n2log 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 {v0,u}.
ER -
English
