Maximum cardinality matching

À propos
Confidentialité
Mentions légales

Graph Chatbot

Publications associées (30)

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

New Algorithmic Paradigms for Discrete Problems using Dynamical Systems and Polynomials

Damian Mateusz Straszak

Optimization is a fundamental tool in modern science. Numerous important tasks in biology, economy, physics and computer science can be cast as optimization problems. Consider the example of machine learning: recent advances have shown that even the most s ...

EPFL2018

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

Network Alignment: Theory, Algorithms, and Applications

Ehsan Kazemi

Networks are central in the modeling and analysis of many large-scale human and technical systems, and they have applications in diverse fields such as computer science, biology, social sciences, and economics. Recently, network mining has been an active a ...

EPFL2016

Group-Sparse Model Selection: Hardness and Relaxations

Volkan Cevher, Anastasios Kyrillidis, Luca Baldassarre, Nirav Bhan

Group-based sparsity models are proven instrumental in linear regression problems for recovering signals from much fewer measurements than standard compressive sensing. The main promise of these models is the recovery of ``interpretable" signals along with ...

Institute of Electrical and Electronics Engineers2016

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

Page 2 sur 2