Adaptive majority problems for restricted query graphs and for weighted sets
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.
A graph G is a diameter graph in R-d if its vertex set is a finite subset in R-d of diameter 1 and edges join pairs of vertices a unit distance apart. It is shown that if a diameter graph G in R-4 contains the complete subgraph K on five vertices, then any ...
We consider the variation of Ramsey numbers introduced by Erdos and Pach [J. Graph Theory, 7 (1983), pp. 137-147], where instead of seeking complete or independent sets we only seek a t-homogeneous set, a vertex subset that induces a subgraph of minimum de ...
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 ...
We consider the problem of reliably connecting an arbitrarily large set of computers (nodes) with communication channels. Reliability means here the ability, for any two nodes, to remain connected (i.e., their ability to communicate) with probability at le ...
A Kneser graph KG(n,k) is a graph whose vertices are in oneto-one correspondence with k -element subsets of [n], with two vertices connected if and only if the corresponding sets do not intersect. A famous result due to Lowisz states that the chromatic num ...
We consider the problem of inferring the hidden structure of high-dimensional dynamic systems from the perspective of graph learning. In particular, we aim at capturing the dynamic relationships between nodes by a sequence of graphs. Our approach is motiva ...
Graphs are now ubiquitous in almost every field of research. Recently, new research areas devoted to the analysis of graphs and data associated to their vertices have emerged. Focusing on dynamical processes, we propose a fast, robust and scalable framewor ...
This paper addresses the problem of compression of 3D point cloud sequences that are characterized by moving 3D positions and color attributes. As temporally successive point cloud frames are similar, motion estimation is key to effective compression of th ...
Institute of Electrical and Electronics Engineers2016
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 ...
Compute-and-forward (CF) is a technique which exploits broadcast and superposition in wireless networks. In this paper, the CF energy benefit is studied for networks with unicast sessions and modeled by connected graphs. This benefit is defined as the rati ...
