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 the complexity and expressive power of conjunctive queries over unranked labeled trees represented using a variety of structure relations such as "child'', "descendant'', and "following'' as well as unary relations for node labels. We establish a ...
This paper improves the Finiasz-Vaudenay construction of TCHo, a hardware-oriented public-key cryptosystem, whose security relies in the hardness of finding a low-weight multiple of a given polynomial, and on the decoding of certain noisy cyclic linear cod ...
Failure location in transparent optical networks is difficult because of the large amount of alarms that a failure can trigger and because of corrupted alarms. One problem that network operators often face is how to set the thresholds in monitoring devices ...
We consider the cocircuit graph GM of an oriented matroid M, which is the 1-skeleton of the cell complex formed by the span of the cocircuits of M. As a result of Cordovil, Fukuda, and Guedes de Oliveira, the isomorphism class of M is not determined by GM, ...
Simultaneous link failures are common in IP networks \cite{Markopoulou04}. In this paper, we develop a technique for locating multiple failures in Service Provider or Enterprise IP networks using active measurement. We propose a two-phased approach that mi ...
The polynomial time algorithm of Lenstra, Lenstra, and Lovász [15] for factoring integer polynomials and variants thereof have been widely used to show that various computational problems in number theory have polynomial time solutions. Among them is the p ...
As more and more genomes are sequenced, evolutionary biologists are becoming increasingly interested in evolution at the level of whole genomes, in scenarios in which the genome evolves through insertions, deletions, and movements of genes along its chromo ...
The poser scheduling problem has been shown to be NP-complete in the general case but in P for a special case by Chang and Edmonds. In this paper, we extend the class of polynomially solvable cases and give some polyhedral characterizations. ...
Precoloring extension problems are known to be NP-complete in several classes of graphs. Here, we consider precolorings of cographs with not only stable sets but also with cliques. We give polynomial time algorithms to extend such a precoloring in an optim ...
In this paper we give a recursive fixpoint characterization of the winning regions in Rabin and Streett games. We use this characterization in two ways. First, we introduce direct Rabin and Streett ranking that are a sound and complete way to characterize ...
