Publications associées à Maximum cardinality matching

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Finding Perfect Matchings in Bipartite Hypergraphs

Chidambaram Annamalai

Haxell's condition [14] is a natural hypergraph analog of Hall's condition, which is a well-known necessary and sufficient condition for a bipartite graph to admit a perfect matching. That is, when Haxell's condition holds it forces the existence of a perf ...

SPRINGER HEIDELBERG2018

Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover

Slobodan Mitrovic, Mohsen Ghaffari

We present O(log log n)-round algorithms in the Massively Parallel Computation (MPC) model, with a(n) memory per machine, that compute a maximal independent set, a 1 + epsilon approximation of maximum matching, and a 2 + epsilon approximation of minimum ve ...

ASSOC COMPUTING MACHINERY2018

A Framework for the Secretary Problem on the Intersection of Matroids

Ola Nils Anders Svensson, Moran Feldman, Rico Zenklusen

The secretary problem became one of the most prominent online selection problems due to its numerous applications in online mechanism design. The task is to select a maximum weight subset of elements subject to given constraints, where elements arrive one- ...

ASSOC COMPUTING MACHINERY2018

Geometric Graph Matching Using Monte Carlo Tree Search

Pascal Fua, Jan Kybic, Miguel Amável Dos Santos Pinheiro

We present an efficient matching method for generalized geometric graphs. Such graphs consist of vertices in space connected by curves and can represent many real world structures such as road networks in remote sensing, or vessel networks in medical imagi ...

Ieee Computer Soc2017

On Computing Breakpoint Distances for Genomes with Duplicate Genes

Bernard Moret, Mingfu Shao

A fundamental problem in comparative genomics is to compute the distance between two genomes in terms of its higher level organization (given by genes or syntenic blocks). For two genomes without duplicate genes, we can easily define (and almost always eff ...

Mary Ann Liebert, Inc2017

Bartering Books to Beers: a Recommender System for Exchange Platforms

Michele Catasta, Jérémie Rappaz, Maria-Luiza Vladarean

Bartering is a timeless practice that is becoming increasingly popular on the Web. Recommending trades for an online bartering platform shares many similarities with traditional approaches to recommendation, in particular the need to model the preferences ...

2017

Converse Bounds for Noisy Group Testing with Arbitrary Measurement Matrices

Volkan Cevher, Jonathan Mark Scarlett

We consider the group testing problem, in which one seeks to identify a subset of defective items within a larger set of items based on a number of noisy tests. While matching achievability and converse bounds are known in several cases of interest for i.i ...

Ieee2016

Growing a Graph Matching from a Handful of Seeds

Matthias Grossglauser, Seyed Hamed Hassani, Ehsan Kazemi

In many graph–mining problems, two networks from different domains have to be matched. In the absence of reliable node attributes, graph matching has to rely on only the link structures of the two networks, which amounts to a generalization of the classic ...

Assoc Computing Machinery2015

Maximum cardinality matching

Graph Chatbot

Chattez avec Graph Search

Finding Perfect Matchings in Bipartite Hypergraphs

Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover

A Framework for the Secretary Problem on the Intersection of Matroids

Geometric Graph Matching Using Monte Carlo Tree Search

On Computing Breakpoint Distances for Genomes with Duplicate Genes

Bartering Books to Beers: a Recommender System for Exchange Platforms

Network Alignment: Theory, Algorithms, and Applications

Converse Bounds for Noisy Group Testing with Arbitrary Measurement Matrices

Growing a Graph Matching from a Handful of Seeds

Team Integration

Finding Perfect Matchings in Bipartite Hypergraphs

Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover

On Computing Breakpoint Distances for Genomes with Duplicate Genes

Geometric Graph Matching Using Monte Carlo Tree Search

Bartering Books to Beers: a Recommender System for Exchange Platforms

Converse Bounds for Noisy Group Testing with Arbitrary Measurement Matrices

Network Alignment: Theory, Algorithms, and Applications

Team Integration

Growing a Graph Matching from a Handful of Seeds

A Framework for the Secretary Problem on the Intersection of Matroids