Increasing the Edge-Connectivity by Contracting a Vertex Subset in Graphs(Graph Algorithm, <Special Section> Foundations of Computer Science)

概要

論文の詳細を見る
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_1, v_2,..., v_n of vertices in V such that, for each i=2, 3,..., n-1, set {v_1, v_2,..., v_i} is an i-maximizer. We give an O(mn+n^2log n) time algorithm for finding such an ordering and then show an application to the source location problem.
社団法人電子情報通信学会の論文
2006-02-01