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.
Routing packets is a central function of multi-hop wireless networks. Traditionally, there have been two paradigms for routing, either based on the geographical coordinates of the nodes (geographic routing), or based on the connectivity graph (topology-bas ...
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 ...
Polar graphs are a natural extension of some classes of graphs like bipartite graphs, split graphs and complements of bipartite graphs. A graph is (s,k)-polar if there exists a partition A,B of its vertex set such that A induces a complete s-partite graph ...
We introduce "derandomized" versions of the tensor product and the zig-zag product, extending the ideas in the derandomized squaring operation of Rozenman and Vadhan. These enable us to obtain graphs with smaller degrees than those obtained using their non ...
It is a long standing open problem to find an explicit description of the stable set polytope of claw-free graphs. Yet more than 20 years after the discovery of a polynomial algorithm for the maximum stable set problem for claw-free graphs, there is even n ...
We consider the coloring problem for mixed graphs, that is, for graphs containing edges and arcs. A mixed coloring c is a coloring such that for every edge [xi,xj], c(xi)=c(xj) and for every arc (xp,xq), $c(x_{p})
We consider a source that transmits information to a receiver by routing it over a communication network represented by a graph and examine rate benefits that finite complexity processing at the intermediate nodes may offer. We show that there exist config ...
Graph Coloring is a very active field of research in graph theory as well as in the domain of the design of efficient heuristics to solve problems which, due to their computational complexity, cannot be solved exactly (no guarantee that an optimal solution ...
It is a long standing open problem to find an explicit description of the stable set polytope of claw-free graphs. Yet more than 20 years after the discovery of a polynomial algorithm for the maximum stable set problem for claw-free graphs, there is even n ...