- 【Updated on May 12, 2025】 Integration of CiNii Dissertations and CiNii Books into CiNii Research
- Trial version of CiNii Research Knowledge Graph Search feature is available on CiNii Labs
- 【Updated on June 30, 2025】Suspension and deletion of data provided by Nikkei BP
- Regarding the recording of “Research Data” and “Evidence Data”
劣モジュラ, 正モジュラ集合関数の多重グラフによる増大法
-
- NAGAMOCHI Hiroshi
- Dept. of Applied Mathematics and Physics, Kyoto University
-
- SHIRAKI Takashi
- Network System TG, C&C Media Research Labs., NEC Corporation
-
- IBARAKI Toshihide
- Dept. of Applied Mathematics and Physics, Kyoto University
Bibliographic Information
- Other Title
-
- Augmenting a Submodular and Posi-modular Set Function by a Multigraph
Search this article
Description
有限集合 V と集合関数 ƒ : 2^V & Z (Zは整数値の集合) が与えれたとき, V上で多重グラフ G=(V, E) を構成し, G のカット関数 c_Gが任意の非空部分集合 X⊂V に対してƒ(X)+c_G(X)≥2を満たすようにする. 関数 f が交差劣モジュラ, 正モジュラであり, かつ三部不等式を満たすとき, 上記の性質を満たすグラフの中で辺数最小のものをO((T_ƒ+1)n^4log n) 時間で求めるアルゴリズムを与える. ここで, n=|V|, T_ƒ与えられたX⊂Vに対しƒ(X)の値を返す時間とする.
Given a finite set V and a set function ƒ : 2^V → Z (Z is the set of integers), we consider the problem of constructing an undirected multigraph G = (V, E) such that the cut function c_G of G satisfies ƒ(X)+c_G(X) ≥ 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((T_ƒ+1)n^4logn) time, where n=|V| and T_ƒ is the time to compute the value of ƒ(X) for a subset X⊂V.
Journal
-
- IPSJ SIG Notes
-
IPSJ SIG Notes 66 41-48, 1999-01-27
Information Processing Society of Japan (IPSJ)
- Tweet
Details 詳細情報について
-
- CRID
- 1573668926953559040
-
- NII Article ID
- 110002812347
-
- NII Book ID
- AN1009593X
-
- ISSN
- 09196072
-
- Text Lang
- en
-
- Data Source
-
- CiNii Articles