Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Concept

Maximum weight matching

Related publications (24)

Microsimulation Framework for Urban Price-Taker Markets

Bilal Farooq

In the context of integrated transportation and other urban engineering infrastructure systems, there are many examples of markets, where consumers exhibit price-taking behaviour. While this behaviour is ubiquitous, the underlying mechanism can be captured ...

2013

Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back

Aleksander Madry

We present an O(m^10/7) = O(m^1.43)-time algorithm for the maximum s-t flow and the minimum s-t cut problems in directed graphs with unit capacities. This is the first improvement over the sparse-graph case of the long-standing O(m min{m^1/2, n^2/3}) runni ...

IEEE2013

On the Performance of Percolation Graph Matching

Matthias Grossglauser, Lyudmila Yartseva

Graph matching is a generalization of the classic graph isomorphism problem. By using only their structures a graph-matching algorithm finds a map between the vertex sets of two similar graphs. This has applications in the de-anonymization of social and in ...

ACM2013

Blockers and transversals in some subclasses of bipartite graphs: When caterpillars are dancing on a grid

Dominique de Werra, Bernard Ries

Given an undirected graph G = (V, E) with matching number nu(G), a d-blocker is a subset of edges B such that nu((V, E \ B))

Elsevier2010