Spectral Hypergraph Sparsifiers of Nearly Linear Size
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.
The graph coloring problem is one of the most famous problems in graph theory and has a large range of applications. It consists in coloring the vertices of an undirected graph with a given number of colors such that two adjacent vertices get different col ...
This thesis concerns optimal packing problems of tubes, or thick curves, where thickness is defined as follows. Three points on a closed space curve define a circle. Taking the infimum over all radii of pairwise-distinct point triples defines the thickness ...
This paper discusses the results of numerical analysis of dispersion of passive solutes in two-dimensional heterogeneous porous formations. Statistics of flow and transport variables, the accuracy and the role of approximations implicit in existing first-o ...
To retrieve scene informations using a single omnidirectional camera, we have based our work on a shape from texture method proposed by Lindeberg. To do so, we have adapted the method of Lindeberg, that was developed for planar images, in order to use it o ...
We present a model for edge updates with restricted randomness in dynamic graph algorithms and a general technique for analyzing the expected running time of an update operation. This model is able to capture the average case in many applications, since (1 ...
This paper solves a longstanding open problem in fully dynamic algorithms: We present the first fully dynamic algorithms that maintain connectivity, bipartiteness, and approximate minimum spanning trees in polylogarithmic time per edge insertion or deletio ...
In this paper we exploit the Continuous Wavelet Transform (CWT) on the two dimensional sphere, introduced previously by two of us, to build associated Discrete Wavelet Frames. We first explore half-continuous frames, i.e., frames where the position remains ...
We present an O(p*n) algorithm for the problem of finding disjoint simple paths of minimum total length between p given pairs of terminals on oriented partial 2-trees with n nodes and positive or negative arc lengths. The algorithm is in O(n) if all termin ...
Self-stabilizing systems can automatically recover from arbitrary state perturbations in finite time. They are therefore well-suited for dynamic, failure prone environments. Spanning-tree construction in distributed systems is a fundamental task which form ...
