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 study complexity and approximation of MIN WEIGHTED NODE COLORING in planar, bipartite and split graphs. We show that this problem is NP-hard in planar graphs, even if they are triangle-free and their maximum degree is bounded above by 4. Then, we prove ...
This paper considers a production planning problem in disassembly systems, which is the problem of determining the quantity and timing of disassembling end-of-use/life products in order to satisfy the demand of their parts or components over a planning hor ...
Computing the weighted coloring number of graphs is a classical topic in combinatorics and graph theory. Recently these problems have again attracted a lot of attention for the class of quasi-line graphs and more specifically fuzzy circular interval graphs ...
In periodic scheduling jobs arrive regularly and have to be executed on one or several machines or processors. An enormous amount of literature has been published on this topic, e.g. the founding work of Liu & Layland [LL73] is among the top cited computer ...
Formation building and keeping among vehicles has been studied for many years, since 1987 with Reynold's rules. This paper presents a control algorithm, based on recent work in graph theory, able to reconfigure static formations of non-holonomic vehicles e ...
Given a point set P in the plane, the Delaunay graph with respect to axis-parallel rectangles is a graph defined on the vertex set P, whose two points p, q is an element of P are connected by an edge if and only if there is a rectangle parallel to the coor ...
The study of genomic inversions (or reversals) has been a mainstay of computational genomics for nearly 20 years. After the initial breakthrough of Hannenhalli and Pevzner, who gave the first polynomial-time algorithm for sorting signed permutations by inv ...
Concurrently exploring both algorithmic and architectural optimizations is a new design paradigm. This survey paper addresses the latest research and future perspectives on the simultaneous development of video coding, processing, and computing algorithms ...
Wireless sensor networks have emerged a few years ago, enabling large scale sensing at low cost. There are many interesting problems related to this new sensing tool: designing robust and small hardware, defining adapted routing protocols, minimizing the e ...
We demonstrate how the scale axis transform can be used to compute a parameterized family of shape skeletons. The skeletons gradually represent only the most important features of a shape, in a scale-adaptive manner. Here a shape O is any bounded open subs ...
