Abstract. Stackelberg pricing of vertex covers in a bipartite graph, with the priceable nodes on one side, reduces to a sequence of maximum flow problems. This was shown by Briest, Hoefer & Krysta [3], leading to an O(n6 ) algorithm. Here n is the number of nodes of the graph. We show how the use of the preflow algorithm gives an O(n4 ) algorithm.
By: Mourad Baïou, Francisco Barahona
Published in: Algorithmica , volume 74, (no 3), pages 1174-1183; 10.1007/s00453-015-9993-x in 2016
Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.
Questions about this service can be mailed to reports@us.ibm.com .