146 citations
- Université Paris Dauphine-PSLFR65 papers
- Centre National de la Recherche ScientifiqueFR52 papers
- Université Paris Sciences et LettresFR27 papers
- University of LuxembourgLU9 papers
- École Nationale de l’Aviation CivileFR6 papers
- Institut Universitaire de FranceFR6 papers
- Laboratoire d'Intégration des Systèmes et des TechnologiesFR5 papers
- AGH University of KrakowPL4 papers
- Commissariat à l'Énergie Atomique et aux Énergies AlternativesFR4 papers
- Hungarian Academy of SciencesHU4 papers
- Korea Advanced Institute of Science and TechnologyKR4 papers
- Laboratoire des Sciences pour la Conception, l'Optimisation et la ProductionFR4 papers
5 papers · 1 filter
An Axiomatic Approach to Robustness in Search Problems with Multiple Scenarios
Patrice Perny, Olivier Spanjaard
This paper is devoted to the search of robust solutions in state space graphs when costs depend on scenarios. We first present axiomatic requirements for preference compatibility w…
Subexponential and FPT-time Inapproximability of Independent Set and Related Problems
Bruno Escoffier, EunJung Kim, Vangelis Th. Paschos
Fixed-parameter algorithms, approximation algorithms and moderately exponential algorithms are three major approaches to algorithms design. While each of them being very active in…
From interpretation of the three classical mechanics actions to the wave function in quantum mechanics
Michel Gondran, Alexandre Gondran
First, we show that there exists in classical mechanics three actions corresponding to different boundary conditions: two well-known actions, the Euler-Lagrange classical action S_…
Some results on more flexible versions of Graph Motif
Romeo Rizzi, Florian Sikora
The problems studied in this paper originate from Graph Motif, a problem introduced in 2006 in the context of biological networks. Informally speaking, it consists in deciding if a…
Scrabble is PSPACE-Complete
Michael Lampis, Valia Mitsou, Karolina Sołtys
In this paper we study the computational complexity of the game of Scrabble. We prove the PSPACE-completeness of a derandomized model of the game, answering an open question of Eri…