Increasing the Edge-Connectivity by Contracting a Vertex Subset in Graphs

Hiroshi NAGAMOCHI

doi:10.1093/ietisy/e89-d.2.744

Increasing the Edge-Connectivity by Contracting a Vertex Subset in Graphs

Hiroshi NAGAMOCHI

Full Text Views

0

Cite this

Summary :

Let G = (V,E) be an edge weighted graph with n vertices and m edges. For a given integer p with 1 < p < n, we call a set X V of p vertices a p-maximizer if X has a property that the edge-connectivity of the graph obtained by contracting X into a single vertex is no less than that of the graph obtained by contracting any other subset of p vertices. In this paper, we first show that there always exists an ordering v₁,v₂,...,v_n of vertices in V such that, for each i = 2,3,...,n - 1, set {v₁,v₂,...,v_i} is an i-maximizer. We give an O(mn + n²log n) time algorithm for finding such an ordering and then show an application to the source location problem.

Publication: IEICE TRANSACTIONS on Information Vol.E89-D No.2 pp.744-750

Publication Date: 2006/02/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1093/ietisy/e89-d.2.744

Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)

Category: Graph Algorithm

Cite this

Copy

Hiroshi NAGAMOCHI, "Increasing the Edge-Connectivity by Contracting a Vertex Subset in Graphs" in IEICE TRANSACTIONS on Information, vol. E89-D, no. 2, pp. 744-750, February 2006, doi: 10.1093/ietisy/e89-d.2.744.
Abstract: Let G = (V,E) be an edge weighted graph with n vertices and m edges. For a given integer p with 1 < p < n, we call a set X V of p vertices a p-maximizer if X has a property that the edge-connectivity of the graph obtained by contracting X into a single vertex is no less than that of the graph obtained by contracting any other subset of p vertices. In this paper, we first show that there always exists an ordering v₁,v₂,...,v_n of vertices in V such that, for each i = 2,3,...,n - 1, set {v₁,v₂,...,v_i} is an i-maximizer. We give an O(mn + n²log n) time algorithm for finding such an ordering and then show an application to the source location problem.
URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e89-d.2.744/_p

Copy

@ARTICLE{e89-d_2_744,
author={Hiroshi NAGAMOCHI, },
journal={IEICE TRANSACTIONS on Information},
title={Increasing the Edge-Connectivity by Contracting a Vertex Subset in Graphs},
year={2006},
volume={E89-D},
number={2},
pages={744-750},
abstract={Let G = (V,E) be an edge weighted graph with n vertices and m edges. For a given integer p with 1 < p < n, we call a set X V of p vertices a p-maximizer if X has a property that the edge-connectivity of the graph obtained by contracting X into a single vertex is no less than that of the graph obtained by contracting any other subset of p vertices. In this paper, we first show that there always exists an ordering v₁,v₂,...,v_n of vertices in V such that, for each i = 2,3,...,n - 1, set {v₁,v₂,...,v_i} is an i-maximizer. We give an O(mn + n²log n) time algorithm for finding such an ordering and then show an application to the source location problem.},
keywords={},
doi={10.1093/ietisy/e89-d.2.744},
ISSN={1745-1361},
month={February},}

Copy

TY - JOUR
TI - Increasing the Edge-Connectivity by Contracting a Vertex Subset in Graphs
T2 - IEICE TRANSACTIONS on Information
SP - 744
EP - 750
AU - Hiroshi NAGAMOCHI
PY - 2006
DO - 10.1093/ietisy/e89-d.2.744
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E89-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2006
AB - Let G = (V,E) be an edge weighted graph with n vertices and m edges. For a given integer p with 1 < p < n, we call a set X V of p vertices a p-maximizer if X has a property that the edge-connectivity of the graph obtained by contracting X into a single vertex is no less than that of the graph obtained by contracting any other subset of p vertices. In this paper, we first show that there always exists an ordering v₁,v₂,...,v_n of vertices in V such that, for each i = 2,3,...,n - 1, set {v₁,v₂,...,v_i} is an i-maximizer. We give an O(mn + n²log n) time algorithm for finding such an ordering and then show an application to the source location problem.
ER -