检索结果-内蒙古大学图书馆

Augmenting Edge-Connectivity between Vertex Subsets

ALGORITHMICA 2014年第1期69卷 130-147页

作者： Ishii, Toshimasa Makino, Kazuhisa Hokkaido Univ Grad Sch Econ Sapporo Hokkaido 0600809 Japan Univ Tokyo Grad Sch Informat Sci & Technol Tokyo 1138656 Japan

Given a directed or undirected graph G=(V,E), a collection of two disjoint subsets of V, and a requirement function , we consider the problem (called area-to-area edge-connectivity augmentation problem) of augmenting G by a smallest number of new edges so that the resulting graph satisfies for all XaS dagger V, with SaS dagger XaS dagger V-T, where d (G) (X) denotes the degree of a vertex set X in G. This problem can be regarded as a natural generalization of the global, local, and node-to-area edge-connectivity augmentation problems. In this paper, we show that there exists a constant c such that the problem is inapproximable within a ratio of , unless P=NP, even restricted to the directed global node-to-area edge-connectivity augmentation or undirected local node-to-area edge-connectivity augmentation. We also provide an -approximation algorithm for the area-to-area edge-connectivity augmentation problem, which is a natural extension of Kortsarz and Nutov's algorithm (Kortsarz and Nutov, J. Comput. Syst. Sci., 74:662-670, 2008). This together with the negative result implies that the problem is -approximable, unless P=NP, which solves open problems for node-to-area edge-connectivity augmentation in Ishii et al. (Algorithmica, 56:413-436, 2010), Ishii and Hagiwara (Discrete Appl. Math., 154:2307-2329, 2006), Miwa and Ito (J. Oper. Res. Soc. Jpn., 47:224-243, 2004). Furthermore, we characterize the node-to-area and area-to-area edge-connectivity augmentation problems as the augmentation problems with modulotone and k-modulotone functions.

关键词： Graph algorithm Approximation algorithm Edge-connectivity modulotone function

来源：评论

学校读者我要写书评

暂无评论

POSI-MODULAR SYSTEMS WITH modulotone REQUIREMENTS UNDER PERMUTATION CONSTRAINTS

引用

DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS 2010年第1期2卷 61-76页

作者： Ishii, Toshimasa Makino, Kazuhisa Otaru Univ Dept Informat & Management Sci Otaru Hokkaido 0478501 Japan Univ Tokyo Grad Sch Informat Sci & Technol Tokyo 1138656 Japan

Given a system (V, f, r) on a finite set V consisting of a posi-modular function f : 2(V)-> R and a modulotone function r : 2(V) -> R, we consider the problem of finding a minimum set R subset of V such that f(X) >= r(X) for all X subset of V -R. The problem, called the transversal problem, was introduced in [M. Sakashita, K. Makino, H. Nagamochi and S. Fujishige, Minimum transversals in posi-modular systems, SIAM J. Discrete Math. 23 (2009) 858871] as a natural generalization of the source location problem and external network problem with edge-connectivity requirements in undirected graphs and hypergraphs. By generalizing [H. Tamura, H. Sugawara, M. Sengoku and S. Shinoda, Plural cover problem on undirected flow networks, IEICE Trans. J81-A (1998) 863-869] for the source location problem, we show that the transversal problem can be solved by a simple greedy algorithm if r is pi-monotone, where a modulotone function r is p-monotone if there exists a permutation pi of V such that the function p(r) : V x 2(V). R associated with r satisfies p(r)(u, W) >= p(r)(v, W) for all W subset of V and u, v is an element of V with pi(u) >= pi(v). Here we show that any modulotone function r can be characterized by p(r) as r(X) = max{p(r)(v, W) | v is an element of X subset of V -W}. We also show the structural properties on the minimal deficient sets W for the transversal problem for p-monotone function r, i.e., there exists a basic tree T for W such that pi(u) <= pi(v) for all arcs (u, v) in T, which, as a corollary, gives an alternative proof for the correctness of the greedy algorithm for the source location problem. Furthermore, we show that a fractional version of the transversal problem can be solved by the algorithm similar to the one for the transversal problem.

关键词： Greedy algorithm posimodular system modulotone function pi-monotonicity

来源：评论

学校读者我要写书评

暂无评论

Augmenting edge-connectivity between vertex subsets 09

Augmenting edge-connectivity between vertex subsets

引用

Proceedings of the Fifteenth Australasian Symposium on Computing: The Australasian Theory - Volume 94

作者： Toshimasa Ishii Kazuhisa Makino Otaru University of Commerce Otaru Japan University of Tokyo Tokyo Japan

ISBN: (纸本)9781920682750

Given a graph G = (V, E) and a requirement function r: W1 x W2 → R+ for two families W1, W2 ⊆ 2V - {θ}, we consider the problem (called area-to-area edge-connectivity augmentation problem) of augmenting G by a smallest number of new edges so that the resulting graph G satisfies δG (X) ≥ r(W1, W2) for all X ⊆ V, W1 ∈ W1, and W2 ∈ W2 with W1 ⊆ X ⊆ V - W2, where δG(X) denotes the degree of a vertex set X in G. This problem can be regarded as a natural generalization of the global, local, and node-to-area edge-connectivity augmentation *** this paper, we show that there exists a constant c such that the problem is inapproximable within a ratio of clog α(W1, W2), unless P=NP, even restricted to the directed global node-to-area edge-connectivity augmentation or undirected local node-to-area edge-connectivity augmentation, where α(W1, W2) denotes the number of pairs W1 ∈ W1 and W2 ∈ W2 with r(W1, W2) > 0. We also provide an O(log α (W1, W2))-approximation algorithm for the area-to-area edge-connectivity augmentation problem. This together with the negative result implies that the problem is Θ(log α (W1, W2))-approximable, unless P=NP, which solves open problems for node-to-area edge-connectivity augmentation (Ishii et al. 2008, Ishii and Hagiwara 2006, Miwa and Ito 2004).Furthermore, we characterize the node-to-area and area-to-area edge-connectivity augmentation problems as the augmentation problems with modulotone and extended modulotone functions.

关键词： approximation algorithm graph algorithm modulotone function edge-connectivity

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：