ALBERT — All Library Books, journals and Electronic Records Telegrafenberg

Hits per page

hit 1 - 1 | 1 hit

Select All Export

Unknown

Stackelberg Bipartite Vertex Cover and the Preflow Algorithm (2015)

Springer

In: Algorithmica

add to mindlist on the mindlist

Details

Publication Date: 2015-03-28

Description: Stackelberg pricing of vertex covers in a bipartite graph, with the priceable nodes on one side of the bipartition, reduces to a sequence of maximum flow problems. This was shown by Briest et al. (Algorithmica 62:733–753, 2012 ), leading to an \(O(n^6)\) algorithm. Here \(n\) is the number of nodes of the graph. We show how the use of the preflow algorithm gives an \(O(n^4)\) algorithm.

Print ISSN: 0178-4617

Electronic ISSN: 1432-0541

Topics: Computer Science , Mathematics

Published by Springer

	Location	Call Number	Expected	Availability

Others were also interested in ...

PAPER CURRENT

S·F·X

Fulltext

hit 1 - 1 | 1 hit