Incremental delay enumeration: space and time

DOI10.1016/J.DAM.2018.06.038MaRDI QIDQ2274091zbMATH OpenOpenAlexWikidataFDO

Authors Florent Capelli, Yann Strozecki

Publication date 19 September 2019

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2018.06.038

zbMATH Keywords

enumerationexponential time hypothesisstructural complexitypolynomial delayincremental time

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Exact enumeration problems, generating functions (05A15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Enumeration of the monomials of a polynomial and related complexity classes
• On enumerating monomials and other combinatorial structures by polynomial interpolation
• Complexity of generation

Cites work

• scientific article; zbMATH DE number 3167451 (Why is no real title available?)
• scientific article; zbMATH DE number 1759419 (Why is no real title available?)
• scientific article; zbMATH DE number 6829393 (Why is no real title available?)
• scientific article; zbMATH DE number 1885142 (Why is no real title available?)
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
• Enumerating all solutions of a Boolean CSP by non-decreasing weight
• Enumeration of the monomials of a polynomial and related complexity classes
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• Interpolating polynomials from their values
• New Results on Monotone Dualization and Generating Hypergraph Transversals
• On enumerating monomials and other combinatorial structures by polynomial interpolation
• On generating all maximal independent sets
• On generating all solutions of generalized satisfiability problems
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• On the Complexity of Some Enumeration Problems for Matroids
• On the Computational Complexity of Algorithms
• On total functions, existence theorems and computational complexity
• Paradigms for parameterized enumeration
• Probabilistic counting algorithms for data base applications
• Reverse search for enumeration
• Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
• The complexity of theorem-proving procedures
• The journey from NP to TFNP hardness
• Undirected connectivity in log-space

Cited in

(6)

• Enumeration complexity of conjunctive queries with functional dependencies
• The complexity of dependency detection and discovery in relational databases
• Efficiently enumerating hitting sets of hypergraphs arising in data profiling
• Constant time enumeration by amortization
• Polynomial-delay enumeration algorithms in set systems
• Enumeration of the monomials of a polynomial and related complexity classes

This page was built for publication: Incremental delay enumeration: space and time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2274091)