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

Hiroshi NAGAMOCHI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E89-D   No.2   pp.744-750
Publication Date: 2006/02/01
Online ISSN: 1745-1361
DOI: 10.1093/ietisy/e89-d.2.744
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
Category: Graph Algorithm
Keyword: 
algorithm,  edge-connectivity,  extreme vertex sets,  graph,  source location problem,  

Full Text: PDF>>
Buy this Article




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 v1,v2,...,vn of vertices in V such that, for each i = 2,3,...,n - 1, set {v1,v2,...,vi} is an i-maximizer. We give an O(mn + n2log n) time algorithm for finding such an ordering and then show an application to the source location problem.