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 interference graph for a procedure in Static Single Assignment (SSA) Form is chordal. Since the k-colorability problem can be solved in polynomial-time for chordal graphs, this result has generated interest in SSA-based heuristics for spilling and coal ...
Graph theory is an important topic in discrete mathematics. It is particularly interesting because it has a wide range of applications. Among the main problems in graph theory, we shall mention the following ones: graph coloring and the Hamiltonian circuit ...
This paper deals with the problem of efficiently computing the optical flow of image sequences acquired by omnidirectional (nearly full field of view) cameras. We formulate the problem in the natural spherical geometry associated with these devices and ext ...
Tucker's lemma states that if we triangulate the unit disc centered at the origin and color the vertices with {1, 1,2, 2} in an antipodal way (if vertical bar z vertical bar = 1, then the sum of the colors of z and -z is zero), then there must be an edge F ...
Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2009
We present an extension of a classical data management subproblem, the page migration. The problem is investigated in dynamic networks, where costs of communication between different nodes may change with time. We construct asymptotically optimal online al ...
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 grap ...
Polar graphs are a common generalization of bipartite, cobipartite, and split graphs. They are defined by the existence of a certain partition of vertices, which is NP-complete to decide for general graphs. It has been recently proved that for cographs, th ...
We consider the following problem: Given a rational matrix A∈Qm×n and a rational polyhedron Q⊆Rm+p, decide if for all vectors b∈Rm, for which there exists an integral z∈Zp suc ...
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 ...
Localization in the presence of malicious beacon nodes is an important problem in wireless networks. Although significant progress has been made on this problem, some fundamental theoretical questions still remain unanswered: in the presence of malicious b ...
