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.
We introduce a family of reductions for removing proper and homogeneous pairs of cliques from a graph G. This family generalizes some routines presented in the literature, mostly in the context of claw-free graphs. These reductions can be embedded in a sim ...
We present a framework for approximating the metric TSP based on a novel use of matchings. Traditionally, matchings have been used to add edges in order to make a given graph Eulerian, whereas our approach also allows for the removal of certain edges leadi ...
The minimum clique partition (MCP) problem is that of partitioning the vertex set of a given graph into a minimum number of cliques. Given n points in the plane, the corresponding unit disk graph (UDG) has these points as vertices, and edges connecting poi ...
One major concern in pervasive wireless applications is location privacy, where malicious eavesdroppers, based on static device identifiers, can continuously track users. As a commonly adopted countermeasure to prevent such identifier-based tracking, devic ...
The proliferation of online social networks, and the concomitant accumulation of user data, give rise to hotly debated issues of privacy, security, and control. One specific challenge is the sharing or public release of anonymized data without accidentally ...
High levels of HIV-1 replication during the chronic phase of infection usually correlate with rapid progression to severe immunodeficiency. However, a minority of highly viremic individuals remains asymptomatic and maintains high CD4+ T cell counts. This t ...
In a drawing of a graph, two edges form an odd pair if they cross each other an odd number of times. A pair of edges is independent if they share no endpoint. For a graph G, let ocr(G) be the smallest number of odd pairs in a drawing of G and let iocr(G) b ...
We consider the Gaussian N-relay diamond net- work, where a source wants to communicate to a destination node through a layer of N-relay nodes. We investigate the following question: What fraction of the capacity can we maintain by using only k out of the ...
Fully automated machine learning methods based on structural magnetic resonance imaging data can assist radiologists in the diagnosis of Alzheimer's disease (AD). These algorithms require large data sets to learn the separation of subjects with and without ...
We address the problem of building a manifold in order to represent a set of geometrically transformed images by selecting a good common sparse approximation of them with parametric atoms. We propose a greedy method to construct a representative pattern su ...
