Record Details

A note on the minimization of symmetric and general submodular functions

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title A note on the minimization of symmetric and general submodular functions
 
Creator NARAYANAN, H
 
Subject cut algorithm
time
symmetric submodular
convex
minimization
 
Description In this paper we relate the minimization problems for general submodular functions and symmetric submodular functions. We characterize the contractions and restrictions of symmetric submodular functions. The latter we show to be the same as posimodular functions. Finally, we prove the equivalence of various symmetric submodular function minimization problems and the general submodular function minimization problem. We also give a preprocessing algorithm for the general submodular function minimization problem which could lead to substantial size reduction. (C) 2003
 
Publisher ELSEVIER SCIENCE BV
 
Date 2011-07-22T19:22:18Z
2011-12-26T12:52:32Z
2011-12-27T05:38:35Z
2011-07-22T19:22:18Z
2011-12-26T12:52:32Z
2011-12-27T05:38:35Z
2003
 
Type Article
 
Identifier DISCRETE APPLIED MATHEMATICS, 131(2), 513-522
0166-218X
http://dx.doi.org/10.1016/S0166-218X(02)00470-5
http://dspace.library.iitb.ac.in/xmlui/handle/10054/6332
http://hdl.handle.net/10054/6332
 
Language en