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 set of phylogenetic trees with overlapping leaf sets is consistent if it can be merged without conflicts into a supertree. In this paper, we study the polynomial-time approximability of two related optimization problems called the maximum rooted triplets ...
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 ...
The idea to use error-correcting codes in order to construct public key cryptosystems was published in 1978 by McEliece [ME1978]. In his original construction, McEliece used Goppa codes, but various later publications suggested the use of different familie ...
The notion of treewidth has seen to be a powerful vehicle for many graph algorithmic studies. A lot of problems, which are in general NP-complete, can be solved in polynomial time for graphs with small treewidth. In the first part of this paper we presen ...
We present a polynomial time approximation scheme for the real-time scheduling problem with fixed priorities when resource augmentation is allowed. For a fixed ε > 0, our algorithmcomputes an assignment using atmost (1+ε)·OPT +1 processors in polynomial ti ...
Uncertain information is commonplace in real-world data management scenarios. The ability to represent large sets of possible instances (worlds) while supporting efficient storage and processing is an important challenge in this context. The recent formali ...
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 ...
This paper addresses a multiprocessor generalization of the preemptive open-shop scheduling problem. The set of processors is partitioned into two groups and the operations of the jobs may require either single processors in either group or simultaneously ...
Register allocation, in high-level synthesis and ASIP design, is the process of determining the number of registers to include in the resulting circuit or processor. The goal is to allocate the minimum number of registers such that no scalar variable is sp ...
Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2007
