853 citations
- Sorbonne UniversitéFR398 papers
- Centre National de la Recherche ScientifiqueFR380 papers
- Université Paris CitéFR136 papers
- Université Pierre-et-Marie-CurieFR97 papers
- University of EdinburghGB89 papers
- Institut national de recherche en sciences et technologies du numériqueFR85 papers
- Université Paris-SaclayFR67 papers
- University of OxfordGB54 papers
- École PolytechniqueFR50 papers
- Sorbonne Paris CitéFR48 papers
- Massachusetts Institute of TechnologyUS45 papers
- Universidade Federal do Rio de JaneiroBR45 papers
22 papers · 1 filter
On the complexity of computing Gröbner bases for weighted homogeneous systems
Jean-Charles Faugère, Mohab Safey El Din, Thibaut Verron
Solving polynomial systems arising from applications is frequently made easier by the structure of the systems. Weighted homogeneity (or quasi-homogeneity) is one example of such a…
Data Reductions and Combinatorial Bounds for Improved Approximation Algorithms
Faisal N. Abu-Khzam, Cristina Bazgan, Morgan Chopin +1
Kernelization algorithms in the context of Parameterized Complexity are often based on a combination of reduction rules and combinatorial insights. We will expose in this paper a s…
Interrupt Timed Automata with Auxiliary Clocks and Parameters
Béatrice Bérard, Serge Haddad, Aleksandra Jovanović +1
Interrupt Timed Automata (ITA) is an expressive timed model, introduced to take into account interruptions, according to levels. Due to this feature, this formalism is incomparable…
A 0.821-ratio purely combinatorial algorithm for maximum -vertex cover in bipartite graphs
Edouard Bonnet, Bruno Escoffier, Vangelis Paschos +1
Our goal in this paper is to propose a \textit{combinatorial algorithm} that beats the only such algorithm known previously, the greedy one. We study the polynomial approximation o…
Probabilistic Opacity for Markov Decision Processes
Béatrice Bérard, Krishnendu Chatterjee, Nathalie Sznajder
Opacity is a generic security property, that has been defined on (non probabilistic) transition systems and later on Markov chains with labels. For a secret predicate, given as a s…
Self-stabilizing algorithms for Connected Vertex Cover and Clique decomposition problems
François Delbot, Christian Laforest, Stephane Rovedakis
In many wireless networks, there is no fixed physical backbone nor centralized network management. The nodes of such a network have to self-organize in order to maintain a virtual…