2001年6月
Augmenting a submodular and posi-modular set function by a multigraph
JOURNAL OF COMBINATORIAL OPTIMIZATION
- ,
- ,
- 巻
- 5
- 号
- 2
- 開始ページ
- 175
- 終了ページ
- 212
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1023/A:1011409332456
- 出版者・発行元
- SPRINGER
Given a finite set V and a set function f : 2(V) bar right arrow Z, we consider the problem of constructing an undirected multigraph G = (V,E) such that the cut function C-G: 2(V) bar right arrow Z of G 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((T-f + 1)n(4) log n) time, where n = |V| and T is the time to compute the value of f(X) for a subset X subset of V.
- リンク情報
-
- DOI
- https://doi.org/10.1023/A:1011409332456
- DBLP
- https://dblp.uni-trier.de/rec/journals/jco/NagamochiSI01
- Web of Science
- https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000168129300003&DestApp=WOS_CPL
- URL
- http://dblp.uni-trier.de/db/journals/jco/jco5.html#journals/jco/NagamochiSI01
- ID情報
-
- DOI : 10.1023/A:1011409332456
- ISSN : 1382-6905
- eISSN : 1573-2886
- DBLP ID : journals/jco/NagamochiSI01
- Web of Science ID : WOS:000168129300003