A Fast Edge-Splitting Algorithm in Edge-Weighted Graphs

Hiroshi NAGAMOCHI

doi:10.1093/ietfec/e89-a.5.1263

A Fast Edge-Splitting Algorithm in Edge-Weighted Graphs

Hiroshi NAGAMOCHI

Full Text Views

0

Share
Cite this

Summary :

Let H be a graph with a designated vertex s, where edges are weighted by nonnegative reals. Splitting edges e={u,s} and e'={s,v} at s is an operation that reduces the weight of each of e and e' by a real δ>0 while increasing the weight of edge {u,v} by δ. It is known that all edges incident to s can be split off while preserving the edge-connectivity of H and that such a complete splitting is used to solve many connectivity problems. In this paper, we give an O(mn+n²log n) time algorithm for finding a complete splitting in a graph with n vertices and m edges.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E89-A No.5 pp.1263-1268

Publication Date: 2006/05/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1093/ietfec/e89-a.5.1263

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Hiroshi NAGAMOCHI, "A Fast Edge-Splitting Algorithm in Edge-Weighted Graphs" in IEICE TRANSACTIONS on Fundamentals, vol. E89-A, no. 5, pp. 1263-1268, May 2006, doi: 10.1093/ietfec/e89-a.5.1263.
Abstract: Let H be a graph with a designated vertex s, where edges are weighted by nonnegative reals. Splitting edges e={u,s} and e'={s,v} at s is an operation that reduces the weight of each of e and e' by a real δ>0 while increasing the weight of edge {u,v} by δ. It is known that all edges incident to s can be split off while preserving the edge-connectivity of H and that such a complete splitting is used to solve many connectivity problems. In this paper, we give an O(mn+n²log n) time algorithm for finding a complete splitting in a graph with n vertices and m edges.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e89-a.5.1263/_p

Copy

@ARTICLE{e89-a_5_1263,
author={Hiroshi NAGAMOCHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Fast Edge-Splitting Algorithm in Edge-Weighted Graphs},
year={2006},
volume={E89-A},
number={5},
pages={1263-1268},
abstract={Let H be a graph with a designated vertex s, where edges are weighted by nonnegative reals. Splitting edges e={u,s} and e'={s,v} at s is an operation that reduces the weight of each of e and e' by a real δ>0 while increasing the weight of edge {u,v} by δ. It is known that all edges incident to s can be split off while preserving the edge-connectivity of H and that such a complete splitting is used to solve many connectivity problems. In this paper, we give an O(mn+n²log n) time algorithm for finding a complete splitting in a graph with n vertices and m edges.},
keywords={},
doi={10.1093/ietfec/e89-a.5.1263},
ISSN={1745-1337},
month={May},}

Copy

TY - JOUR
TI - A Fast Edge-Splitting Algorithm in Edge-Weighted Graphs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1263
EP - 1268
AU - Hiroshi NAGAMOCHI
PY - 2006
DO - 10.1093/ietfec/e89-a.5.1263
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E89-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2006
AB - Let H be a graph with a designated vertex s, where edges are weighted by nonnegative reals. Splitting edges e={u,s} and e'={s,v} at s is an operation that reduces the weight of each of e and e' by a real δ>0 while increasing the weight of edge {u,v} by δ. It is known that all edges incident to s can be split off while preserving the edge-connectivity of H and that such a complete splitting is used to solve many connectivity problems. In this paper, we give an O(mn+n²log n) time algorithm for finding a complete splitting in a graph with n vertices and m edges.
ER -