Incremental delay enumeration: space and time
DOI10.1016/J.DAM.2018.06.038zbMATH Open1419.05014OpenAlexW2888663614WikidataQ129341712 ScholiaQ129341712MaRDI QIDQ2274091FDOQ2274091
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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Exact enumeration problems, generating functions (05A15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- On the Computational Complexity of Algorithms
- Undirected connectivity in log-space
- Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
- Title not available (Why is that?)
- The complexity of theorem-proving procedures
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- On generating all solutions of generalized satisfiability problems
- Reverse search for enumeration
- Interpolating polynomials from their values
- On generating all maximal independent sets
- Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
- On total functions, existence theorems and computational complexity
- Title not available (Why is that?)
- Boltzmann Samplers for the Random Generation of Combinatorial Structures
- New Results on Monotone Dualization and Generating Hypergraph Transversals
- Probabilistic counting algorithms for data base applications
- Enumeration of the monomials of a polynomial and related complexity classes
- On enumerating monomials and other combinatorial structures by polynomial interpolation
- A complexity theory for hard enumeration problems
- On the Complexity of Some Enumeration Problems for Matroids
- Enumerating all solutions of a Boolean CSP by non-decreasing weight
- Title not available (Why is that?)
- Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
- Title not available (Why is that?)
- Paradigms for parameterized enumeration
- The Journey from NP to TFNP Hardness
Cited In (5)
- The complexity of dependency detection and discovery in relational databases
- Enumeration of the monomials of a polynomial and related complexity classes
- Efficiently enumerating hitting sets of hypergraphs arising in data profiling
- Enumeration complexity of conjunctive queries with functional dependencies
- Polynomial-delay enumeration algorithms in set systems
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)
