Augmenting a Submodular and Posi-modular Set Function by a Multigraph期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

Augmenting a Submodular and Posi-modular Set Function by a Multigraph

Authors:	Hiroshi Nagamochi Takashi Shiraki Toshihide Ibaraki

Institution:	(1) Department of Information and Computer Sciences, Toyohashi University of Technology, Tempaku, Toyohashi, 441-8580, Japan;(2) 1st Laboratory, Development Laboratories, NEC Networks Abiko, Chiba, 270-1198, Japan;(3) Department of Applied Mathematics and Physics, Kyoto University, Sakyo, Kyoto, 606-8501, Japan

Abstract:	Given a finite set V and a set function $f:2^V \mapsto Z$ , we consider the problem of constructing an undirected multigraph G = (V,E) such that the cut function $C_G :2^V \mapsto Z{\text{ of }}G{\text{ and }}f$ together has value at least 2 for all non-empty and proper subsets of V. If f is intersecting submodular and posi-modular, and satisfies the tripartite inequality, then we show that such a multigraph G with the minimum number of edges can be found in $O\left( {\left( {T_f + 1} \right)n^4 \log n} \right)$ time, where $n = \left\| V \right\|{\text{ and }}T_f$ is the time to compute the value of f(X) for a subset $X \subset V$ .

Keywords:	algorithms submodular function posi-modular function minimum cut edge-connectivity undirected graph edge-splitting graph augmentation
本文献已被 SpringerLink 等数据库收录！