Publications related to Association Generation in Synthetic Population for Transportation Applications: Graph-Theoretic Solution

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

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

d-Transversals of stable sets and vertex covers in weighted bipartite graphs

Dominique de Werra, Bernard Ries

Let G=(V,E)G=(V,E) be a graph in which every vertex v∈Vv∈V has a weight w(v)⩾0w(v)⩾0 and a cost c(v)⩾0c(v)⩾0. Let SGSG be the family of all maximum-weight stable sets in G . For any integer d⩾0d⩾0, a minimum d-transversal in the graph G with respect to SGS ...

2012

Bipartite Graphs as Models of Population Structures in Evolutionary Multiplayer Games

Yannick Rochat

By combining evolutionary game theory and graph theory, “games on graphs” study the evolutionary dynamics of frequency-dependent selection in population structures modeled as geographical or social networks. Networks are usually represented by means of uni ...

Public Library of Science2012

Minimum d-blockers and d-transversals in graphs

Dominique de Werra

We consider a set V of elements and an optimization problem on V: the search for a maximum (or minimum) cardinality subset of V verifying a given property a"similar to. A d-transversal is a subset of V which intersects any optimum solution in at least d el ...

2011

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))

2010

Blockers and transversals

Dominique de Werra, Bernard Ries, Rico Zenklusen

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. ...

2009

Weighted coloring on planar, bipartite and split graphs: Complexity and approximation

Dominique de Werra

We study complexity and approximation of MIN WEIGHTED NODE COLORING in planar, bipartite and split graphs. We show that this problem is NP-hard in planar graphs, even if they are triangle-free and their maximum degree is bounded above by 4. Then, we prove ...

2009

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

Association Generation in Synthetic Population for Transportation Applications: Graph-Theoretic Solution

Graph Chatbot

Chat with Graph Search

On the Performance of Percolation Graph Matching

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

d-Transversals of stable sets and vertex covers in weighted bipartite graphs

Bipartite Graphs as Models of Population Structures in Evolutionary Multiplayer Games

Minimum d-blockers and d-transversals in graphs

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

Blockers and transversals

Weighted coloring on planar, bipartite and split graphs: Complexity and approximation

Bicolored matchings in some classes of graphs

Variations of coloring problems related to scheduling and discrete tomography

Minimum d-blockers and d-transversals in graphs

On the Performance of Percolation Graph Matching

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

d-Transversals of stable sets and vertex covers in weighted bipartite graphs

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

Blockers and transversals

Bipartite Graphs as Models of Population Structures in Evolutionary Multiplayer Games

Weighted coloring on planar, bipartite and split graphs: Complexity and approximation

Bicolored matchings in some classes of graphs

Variations of coloring problems related to scheduling and discrete tomography