Concept

Matching (graph theory)

Related publications (189)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Population Sensing Using Mobile Devices

Farid Movahedi Naini

In our daily lives, our mobile phones sense our movements and interactions via a rich set of embedded sensors such as a GPS, Bluetooth, accelerometers, and microphones. This enables us to use mobile phones as agents for collecting spatio-temporal data. The ...

EPFL2014

Exponentiality of the exchange algorithm for finding another room-partitioning

Laura Sanità

Let T be a triangulated surface given by the list of vertex-triples of its triangles, called rooms. A room-partitioning for T is a subset R of the rooms such that each vertex of T is in exactly one room in R. Given a room-partitioning R for T, the exchange ...

Elsevier Science Bv2014

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

Michel Bierlaire, Bilal Farooq, Dimitrios Efthymiou, Paul Richard Anderson

The generation of synthetic populations through simulation methods is an important research topic and has a key application in agent-based modeling of transport and land use. The next step in this research area is the generation of complete synthetic house ...

Natl Acad Sciences2014

Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition

Yuri Faenza, Gautier Stauffer

We propose an algorithm for solving the maximum weighted stable set problem on claw-free graphs that runs in O(vertical bar V vertical bar (vertical bar E vertical bar+vertical bar V vertical bar log vertical bar V vertical bar))-time, drastically improvin ...

Assoc Computing Machinery2014

Frequency capping in online advertising

Moran Feldman

We study the following online problem. There are n advertisers. Each advertiser has a total demand and a value for each supply unit. Supply units arrive one by one in an online fashion, and must be allocated to an agent immediately. Each unit is associated ...

Springer2014

Free-Shape Polygonal Object Localization

Pascal Fua, Christos Marios Christoudias, Xiaolu Sun

Polygonal objects are prevalent in man-made scenes. Early approaches to detecting them relied mainly on geometry while subsequent ones also incorporated appearance-based cues. It has recently been shown that this could be done fast by searching for cycles ...

Springer-Verlag Berlin2014

Aggregating information from the crowd

Florent Frédéric Garcin

With an ever-growing amount of data generated on the web, aggregating information from the crowd into meaningful knowledge has become crucial to companies in order to create a competitive edge. Not only companies, but also organizations and governments can ...

EPFL2014

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

A Bayesian Method for Matching Two Similar Graphs without Seeds

Matthias Grossglauser, Pedram Pedarsani

Approximate graph matching (AGM) refers to the problem of mapping the vertices of two structurally similar graphs, which has applications in social networks, computer vision, chemistry, and biology. Given its computational cost, AGM has mostly been limited ...

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