Record Details

A note on optimal covering augmentation for graphic polymatroids

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title A note on optimal covering augmentation for graphic polymatroids
 
Creator PATKAR, SB
NARAYANAN, H
 
Subject algorithms
network
flow
algorithms
combinatorial problems
analysis of algorithms
design of algorithms
graph
polymatroid
 
Description We present a simple and efficient algorithm for the problem of optimal covering augmentation for graphic polymatroids. We make a simple modification to the greedy algorithm for polymatroids of Edmonds [Proc. Calgary Internat. Conf. on Combinatorial Structures, 1970, pp. 69-87] so that it terminates in fewer steps. Our algorithm is far simpler yet as efficient as the previous best algorithm of Gabow [J. Algorithms 26 (1998) 48-86]. It may also be noted that our algorithm is indeed an efficient algorithm for the general problem of performing min-cost augmentation of a feasible vector to a base of a graphic polymatroid. (C) 2001
 
Publisher ELSEVIER SCIENCE BV
 
Date 2011-07-22T19:19:29Z
2011-12-26T12:52:32Z
2011-12-27T05:38:34Z
2011-07-22T19:19:29Z
2011-12-26T12:52:32Z
2011-12-27T05:38:34Z
2001
 
Type Article
 
Identifier INFORMATION PROCESSING LETTERS, 79(6), 285-290
0020-0190
http://dx.doi.org/10.1016/S0020-0190(01)00140-5
http://dspace.library.iitb.ac.in/xmlui/handle/10054/6330
http://hdl.handle.net/10054/6330
 
Language en