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

Concept

Fractional matching

Publications associées (27)

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

Mirror Match: Reliable Feature Point Matching Without Geometric Constraints

Sabine Süsstrunk, Stefan Winkler

Many algorithms have been proposed to solve the problem of matching feature points in two or more images using geometric assumptions to increase the robustness of the matching. However, these assumptions do not always hold; in particular, few methods addre ...

2013

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

Blockers and transversals

Dominique de Werra, Bernard Ries

Given an undirected graph G = (V, E) with matching number v(G), we define d-blockers as subsets of edges B such that nu((V, E \ B)) = d. ...

Elsevier2009

Bicolored matchings in some classes of graphs

Dominique de Werra, Bernard Ries

We consider the problem of finding in a graph a set

R

of edges to be colored in red so that there are maximum matchings having some prescribed numbers of red edges. For regular bipartite graphs with

n

nodes on each side, we give sufficient conditions f ...

2007

Variations of coloring problems related to scheduling and discrete tomography

Bernard Ries

The graph coloring problem is one of the most famous problems in graph theory and has a large range of applications. It consists in coloring the vertices of an undirected graph with a given number of colors such that two adjacent vertices get different col ...

EPFL2007

Publications associées (27)

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

Aleksander Madry

IEEE2013

Mirror Match: Reliable Feature Point Matching Without Geometric Constraints

Sabine Süsstrunk, Stefan Winkler

2013

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

Blockers and transversals

Dominique de Werra, Bernard Ries

Given an undirected graph G = (V, E) with matching number v(G), we define d-blockers as subsets of edges B such that nu((V, E \ B)) = d. ...

Elsevier2009

Bicolored matchings in some classes of graphs

Dominique de Werra, Bernard Ries

We consider the problem of finding in a graph a set

R

of edges to be colored in red so that there are maximum matchings having some prescribed numbers of red edges. For regular bipartite graphs with

n

nodes on each side, we give sufficient conditions f ...

2007

Variations of coloring problems related to scheduling and discrete tomography

Bernard Ries

EPFL2007

Fractional matching

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

Mirror Match: Reliable Feature Point Matching Without Geometric Constraints

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

Sponsored Search, Market Equilibria, and the Hungarian Method

Blockers and transversals

Bicolored matchings in some classes of graphs

Variations of coloring problems related to scheduling and discrete tomography

Graph Chatbot

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

Mirror Match: Reliable Feature Point Matching Without Geometric Constraints

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

Sponsored Search, Market Equilibria, and the Hungarian Method

Blockers and transversals

Bicolored matchings in some classes of graphs

Variations of coloring problems related to scheduling and discrete tomography