New Notions and Constructions of Sparsification for Graphs and Hypergraphs
Graph Chatbot
Chattez avec Graph Search
Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.
AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.
A graph drawn in the plane is called k-quasi-planar if it does not contain k pair-wise crossing edges. It has been conjectured for a long time that for every fixed k, the maximum number of edges of a k-quasi-planar graph with n vertices is O(n). The best k ...
A number of new localized, multiscale transforms have recently been introduced to analyze data residing on weighted graphs. In signal processing tasks such as regularization and compression, much of the power of classical wavelets on the real line is deriv ...
Shortest paths are not always simple. In planar networks, they can be very different from those with the smallest number of turns - the simplest paths. The statistical comparison of the lengths of the shortest and simplest paths provides a non trivial and ...
We propose a method for learning dictionaries towards sparse approximation of signals defined on vertices of arbitrary graphs. Dictionaries are expected to describe effectively the main spatial and spectral components of the signals of interest, so that th ...
In this paper we deal with the critical node problem (CNP), i.e., the problem of searching for a given number K of nodes in a graph G, whose removal minimizes the (weighted or unweighted) number of connections between pairs of nodes in the residual graph. ...
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 ...
We analyse the results of our experimental laboratory approximation of motorways networks with slime mould Physarum polycephalum. Motorway networks of fourteen geographical areas are considered: Australia, Africa, Belgium, Brazil, Canada, China, Germany, I ...
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 ...
We present an O(m^10/7) = O(m^1.43)-time algorithm for the maximum s-t flow and the minimum s-t cut problems in directed graphs with unit capacities. This is the first improvement over the sparse-graph case of the long-standing O(m min{m^1/2, n^2/3}) runni ...
We introduce a precise interprocedural effect analysis for programs with mutable state, dynamic object allocation, and dynamic dispatch. Our analysis is precise even in the presence of dynamic dispatch where the context-insensitive estimate on the number o ...
