Incremental delay enumeration: space and time
From MaRDI portal
Publication:2274091
DOI10.1016/j.dam.2018.06.038zbMath1419.05014OpenAlexW2888663614MaRDI QIDQ2274091
Yann Strozecki, Florent Capelli
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
Analysis of algorithms and problem complexity (68Q25) Exact enumeration problems, generating functions (05A15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Efficiently enumerating hitting sets of hypergraphs arising in data profiling ⋮ The complexity of dependency detection and discovery in relational databases ⋮ Enumeration complexity of conjunctive queries with functional dependencies
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On enumerating monomials and other combinatorial structures by polynomial interpolation
- On total functions, existence theorems and computational complexity
- Interpolating polynomials from their values
- Probabilistic counting algorithms for data base applications
- On generating all maximal independent sets
- Reverse search for enumeration
- A complexity theory for hard enumeration problems
- Paradigms for parameterized enumeration
- Enumerating All Solutions of a Boolean CSP by Non-decreasing Weight
- Enumeration of the Monomials of a Polynomial and Related Complexity Classes
- Undirected connectivity in log-space
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
- Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
- On generating all solutions of generalized satisfiability problems
- The Journey from NP to TFNP Hardness
- Boltzmann Samplers for the Random Generation of Combinatorial Structures
- New Results on Monotone Dualization and Generating Hypergraph Transversals
- On the Computational Complexity of Algorithms
- Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
- On the Complexity of Some Enumeration Problems for Matroids
- The complexity of theorem-proving procedures
