Publications related to Matching (graph theory)

Reconstruction using approximate message passing methods

Paul Hurley, Matthieu Martin Jean-André Simeoni, Giovanni Cherubini, Sanaz Kazemi

The present invention is notably directed to a computer-implemented method for image reconstruction. The method comprises: accessing elements that respectively correspond to measurement values, which can be respectively mapped to measurement nodes; and per ...

2017

Unsupervised Camera Localization in Crowded Spaces

Alexandre Massoud Alahi

Existing camera networks in public spaces such as train terminals or malls can help social robots to navigate crowded scenes. However, the localization of the cameras is required, i.e., the positions and poses of all cameras in a unique reference. In this ...

2017

Partial Recovery Bounds for the Sparse Stochastic Block Model

Volkan Cevher, Jonathan Mark Scarlett

In this paper, we study the information-theoretic limits of community detection in the symmetric two-community stochastic block model, with intra-community and inter-community edge probabilities

\frac{a}{n}

and

\frac{b}{n}

respectively. We consider the ...

Ieee2016

Induced Matchings In Graphs Of Degree At Most 4

Viet Hang Nguyen

For a graph G, let nu(s)(G) be the strong matching number of G. We prove the sharp bound nu(s)(G) >= n(G)/9 for every graph G of maximum degree at most 4 and without isolated vertices that does not contain a certain blown-up 5-cycle as a component. This re ...

Siam Publications2016

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

Independence number of generalized Petersen graphs

Javad Ebrahimi Boroojeni

Determining the size of a maximum independent set of a graph G, denoted by alpha(G), is an NP-hard problem. Therefore many attempts are made to find upper and lower bounds, or exact values of alpha(G) for special classes of graphs. This paper is aimed towa ...

Charles Babbage Res Ctr2016

A Polynomial Regularity Lemma For Semialgebraic Hypergraphs And Its Applications In Geometry And Property Testing

János Pach

In this paper, we prove several extremal results for geometrically defined hypergraphs. In particular, we establish an improved lower bound, single exponentially decreasing in k, on the best constant delta > 0 such that the vertex classes P-1,...,P-k of ev ...

Society for Industrial and Applied Mathematics2016

On the Difficulty of Selecting Ising Models with Approximate Recovery

Volkan Cevher, Jonathan Mark Scarlett

In this paper, we consider the problem of estimating the underlying graph associated with an Ising model given a number of independent and identically distributed samples. We adopt an approximate recovery criterion that allows for a number of missed edges ...

Ieee-Inst Electrical Electronics Engineers Inc2016

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

Asymptotically Optimal Matching of Multiple Sequences to Source Distributions and Training Sequences

Jayakrishnan Unnikrishnan

Consider a finite set of sources, each producing independent identically distributed observations that follow a unique probability distribution on a finite alphabet. We study the problem of matching a finite set of observed sequences to the set of sources ...

Institute of Electrical and Electronics Engineers2015

Matching (graph theory)

Graph Chatbot

Chat with Graph Search

Reconstruction using approximate message passing methods

Unsupervised Camera Localization in Crowded Spaces

Partial Recovery Bounds for the Sparse Stochastic Block Model

Induced Matchings In Graphs Of Degree At Most 4

Network Alignment: Theory, Algorithms, and Applications

Independence number of generalized Petersen graphs

A Polynomial Regularity Lemma For Semialgebraic Hypergraphs And Its Applications In Geometry And Property Testing

On the Difficulty of Selecting Ising Models with Approximate Recovery

Converse Bounds for Noisy Group Testing with Arbitrary Measurement Matrices

Asymptotically Optimal Matching of Multiple Sequences to Source Distributions and Training Sequences

A Polynomial Regularity Lemma For Semialgebraic Hypergraphs And Its Applications In Geometry And Property Testing

Independence number of generalized Petersen graphs

Reconstruction using approximate message passing methods

Converse Bounds for Noisy Group Testing with Arbitrary Measurement Matrices

Asymptotically Optimal Matching of Multiple Sequences to Source Distributions and Training Sequences

Partial Recovery Bounds for the Sparse Stochastic Block Model

Network Alignment: Theory, Algorithms, and Applications

Induced Matchings In Graphs Of Degree At Most 4

On the Difficulty of Selecting Ising Models with Approximate Recovery

Unsupervised Camera Localization in Crowded Spaces