Incremental delay enumeration: Space and time

Capelli, Florent; Strozecki, Yann

Type de document :

Article dans une revue scientifique: Article original

DOI :

10.1016/j.dam.2018.06.038

Titre :

Incremental delay enumeration: Space and time

Auteur(s) :

Capelli, Florent [Auteur]

Linking Dynamic Data [LINKS]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Strozecki, Yann [Auteur]
Données et algorithmes pour une ville intelligente et durable - DAVID [DAVID]

Titre de la revue :

Discrete Applied Mathematics

Éditeur :

Elsevier

Date de publication :

2018-08

ISSN :

0166-218X

Mot(s)-clé(s) en anglais :

Enumeration
Incremental time
Polynomial delay
Structural complexity
Exponential time hypothesis

Discipline(s) HAL :

Informatique [cs]
Informatique [cs]/Complexité [cs.CC]

Résumé en anglais : [en]

We investigate the relationship between several enumeration complexity classes andfocus in particular on problems having enumeration algorithms with incremental andpolynomial delay ( IncP andDelayP respectively). We show ...
Lire la suite >We investigate the relationship between several enumeration complexity classes andfocus in particular on problems having enumeration algorithms with incremental andpolynomial delay ( IncP andDelayP respectively). We show that, for some algorithms, wecan turn an average delay into a worst case delay without increasing the space complexity,suggesting that IncP1 = DelayP even with polynomially bounded space. We use theExponential Time Hypothesis to exhibit a strict hierarchy inside IncP which gives the firstseparation of DelayP andIncP. Finally we relate the uniform generation of solutions toprobabilistic enumeration algorithms with polynomial delay and polynomial space.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Projet ANR :

Requêtes d'Agrégation

Collections :

Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL

Fichiers

http://arxiv.org/pdf/1703.01928
Accès libre
Accéder au document

https://hal.inria.fr/hal-01923091/document
Accès libre
Accéder au document

https://hal.inria.fr/hal-01923091/document
Accès libre
Accéder au document

https://hal.inria.fr/hal-01923091/document
Accès libre
Accéder au document

document
Accès libre
Accéder au document

S0166218X18304001.pdf
Accès libre
Accéder au document

1703.01928
Accès libre
Accéder au document

document
Accès libre
Accéder au document

S0166218X18304001.pdf
Accès libre
Accéder au document

Incremental delay enumeration: Space and time BibTeX CSV Excel RIS

Fichiers

Incremental delay enumeration: Space and time

BibTeX

CSV

Excel

RIS