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.
We describe a new sampling-based method to determine cuts in an undirected graph. For a graph (V, E), its cycle space is the family of all subsets of E that have even degree at each vertex. We prove that with high probability, sampling the cycle space iden ...
We study the time complexity for deterministic broadcasting algorithms in mobile radio networks. The broadcast operation consists of a source node successfully communicating its message to every other node. In multi-hop radio networks such as MANETs, the m ...
NODE-WEIGHTED STEINER FOREST is the following problem: Given an undirected graph, a set of pairs of terminal vertices, a weight function on the vertices, find a minimum weight set of vertices that includes and connects each pair of terminals. We consider t ...
In this note we consider two coloring problems in mixed graphs, i.e., graphs containing edges and arcs. We show that they are both NP-complete in cubic planar bipartite graphs. This answers an open question from \cite{Ries2}. ...
We are interested in coloring the vertices of a mixed graph, i.e., a graph containing edges and arcs. We consider two different coloring problems: in the first one we want adjacent vertices to have different colors and the tail of an arc to get a color str ...
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 paper presents a general class of gossip-based averaging algorithms, which are inspired from Uniform Gossip [1]. While Uniform Gossip works synchronously on complete graphs, weighted gossip algorithms allow asynchronous rounds and converge on any conn ...
We are interested in coloring the edges of a mixed graph. i.e., a graph containing unoriented and oriented edges. This problem is related to a communication problem in job-shop scheduling systems. In this paper we give general bounds oil the number of requ ...