Incremental delay enumeration: Space and time

Capelli, Florent; Strozecki, Yann

Document type :

Article dans une revue scientifique: Article original

DOI :

10.1016/j.dam.2018.06.038

Title :

Incremental delay enumeration: Space and time

Author(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]

Journal title :

Discrete Applied Mathematics

Publisher :

Elsevier

Publication date :

2018-08

ISSN :

0166-218X

English keyword(s) :

Enumeration
Incremental time
Polynomial delay
Structural complexity
Exponential time hypothesis

HAL domain(s) :

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

English abstract : [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 ...
Show more >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.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

ANR Project :

Requêtes d'Agrégation

Collections :

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

Source :

Harvested from HAL

Files

http://arxiv.org/pdf/1703.01928
Open access
Access the document

https://hal.inria.fr/hal-01923091/document
Open access
Access the document

https://hal.inria.fr/hal-01923091/document
Open access
Access the document

https://hal.inria.fr/hal-01923091/document
Open access
Access the document

document
Open access
Access the document

S0166218X18304001.pdf
Open access
Access the document

1703.01928
Open access
Access the document

document
Open access
Access the document

S0166218X18304001.pdf
Open access
Access the document

Incremental delay enumeration: Space and time BibTeX CSV Excel RIS

Files

Incremental delay enumeration: Space and time

BibTeX

CSV

Excel

RIS