Paper Info
Title
Augmenting a Submodular and Posi-modular Set Function by a Multigraph
Abstract
Given a finite set V and a set function <img src="/fulltext-image.asp?format=htmlnonpaginated&src=X434U25873152121_html\10878_2004_Article_333481_TeX2GIFIE1.gif" border="0" alt=" $$f:2^V \mapsto Z$$ " />, we consider the problem of constructing an undirected multigraph G = (V,E) such that the cut function <img src="/fulltext-image.asp?format=htmlnonpaginated&src=X434U25873152121_html\10878_2004_Article_333481_TeX2GIFIE2.gif" border="0" alt=" $$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 <img src="/fulltext-image.asp?format=htmlnonpaginated&src=X434U25873152121_html\10878_2004_Article_333481_TeX2GIFIE3.gif" border="0" alt=" $$O\left( {\left( {T_f + 1} \right)n^4 \log n} \right)$$ " /> time, where <img src="/fulltext-image.asp?format=htmlnonpaginated&src=X434U25873152121_html\10878_2004_Article_333481_TeX2GIFIE4.gif" border="0" alt=" $$n = \left| V \right|{\text{ and }}T_f$$ " /> is the time to compute the value of f(X) for a subset <img src="/fulltext-image.asp?format=htmlnonpaginated&src=X434U25873152121_html\10878_2004_Article_333481_TeX2GIFIE5.gif" border="0" alt=" $$X \subset V$$ " />.
Year
DOI
Venue
2001
10.1023/A:1011409332456
J. Comb. Optim.
Keywords
Field
DocType
algorithms,submodular function,posi-modular function,minimum cut,edge-connectivity,undirected graph,edge-splitting,graph augmentation
Set function,Discrete mathematics,Mathematical optimization,Combinatorics,Finite set,Multigraph,Submodular set function,Connectivity,Mathematics
Journal
Volume
Issue
ISSN
5
2
1573-2886
Citations 
PageRank 
References 
2
0.39
11
Authors
3
Name
Order
Citations
PageRank
Hiroshi Nagamochi11513174.40
Takashi Shiraki271.35
Toshihide Ibaraki32593385.64