Publications related to Adaptive majority problems for restricted query graphs and for weighted sets

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.

Lower bounds on the obstacle number of graphs

János Pach, Doemoetoer Palvoelgyi, Padmini Mukkamala

Given a graph G, an obstacle representation of G is a set of points in the plane representing the vertices of G, together with a set of connected obstacles such that two vertices of G are joined by an edge if and only if the corresponding points can be con ...

2012

Graph Transformations preserving the stability number

Dominique de Werra

We analyze the relations between several graph transformations that were introduced to be used in procedures determining the stability number of a graph. We show that all these transformations can be decomposed into a sequence of edge deletions and twin de ...

Elsevier Science Bv2012

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

Sequential Group Testing with Graph Constraints

Amin Karbasi, Morteza Zadimoghaddam

In conventional group testing, the goal is to detect a small subset of defecting items

\mathcal{D}

in a large population

\mathcal{N}

by grouping \textit{arbitrary} subset of

\mathcal{N}

into different pools. The result of each group test $\mathcal{T} ...

Ieee2012

Finite graphs and amenability

Gábor Elek

Hyperfiniteness or amenability of measurable equivalence relations and group actions has been studied for almost fifty years. Recently, unexpected applications of hyperfiniteness were found in computer science in the context of testability of graph propert ...

Academic Press Inc Elsevier Science2012

Robust Non-Rigid Registration of 2D and 3D Graphs

Pascal Fua, Jan Kybic, Przemyslaw Rafal Glowacki

We present a new approach to matching graphs embedded in R2 or R3. Unlike earlier methods, our approach does not rely on the similarity of local appearance features, does not require an initial alignment, can handle partial matches, and can cope with non-l ...

2012

Methods for Clustering Multi-Layer Graphs in Mobile Networks

Pascal Frossard, Pierre Vandergheynst, Xiaowen Dong

Clustering on graphs has been studied extensively for years due to its numerous applications. However, in contrast to the classic problems, clustering in mobile and online social networks brings new challenges. In these scenarios, it is common that observa ...

2011

Conway's conjecture for monotone thrackles

János Pach

A drawing of a graph in the plane is called a thrackle if every pair of edges meet precisely once, either at a common vertex or at a proper crossing. According to Conway's conjecture, every thrackle has at most as many edges as vertices. We prove this conj ...

Mathematical Association of America2011

Sequential Group Testing with Graph Constraints

Amin Karbasi, Morteza Zadimoghaddam

In conventional group testing, the goal is to detect a small subset of defecting items

\mathcal{D}

in a large population

\mathcal{N}

by grouping \textit{arbitrary} subset of

\mathcal{N}

into different pools. The result of each group test $\mathcal{T} ...

Ieee2012

Adaptive majority problems for restricted query graphs and for weighted sets

Graph Chatbot

Chat with Graph Search

Lower bounds on the obstacle number of graphs

Graph Transformations preserving the stability number

Bipartite Graphs as Models of Population Structures in Evolutionary Multiplayer Games

Sequential Group Testing with Graph Constraints

Finite graphs and amenability

Robust Non-Rigid Registration of 2D and 3D Graphs

Disjoint homometric sets in graphs

Every graph admits an unambiguous bold drawing

Methods for Clustering Multi-Layer Graphs in Mobile Networks

Conway's conjecture for monotone thrackles

Conway's conjecture for monotone thrackles

Graph Transformations preserving the stability number

Methods for Clustering Multi-Layer Graphs in Mobile Networks

Every graph admits an unambiguous bold drawing

Bipartite Graphs as Models of Population Structures in Evolutionary Multiplayer Games

Sequential Group Testing with Graph Constraints

Finite graphs and amenability

Robust Non-Rigid Registration of 2D and 3D Graphs

Disjoint homometric sets in graphs

Lower bounds on the obstacle number of graphs