Enumerating models of DNF faster: breaking the dependency on the formula size
From MaRDI portal
Publication:1983134
DOI10.1016/j.dam.2020.02.014OpenAlexW3010237674MaRDI QIDQ1983134
Yann Strozecki, Florent Capelli
Publication date: 15 September 2021
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1810.04006
Searching and sorting (68P10) Exact enumeration problems, generating functions (05A15) Database theory (68P15) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On enumerating monomials and other combinatorial structures by polynomial interpolation
- Linear delay enumeration and monadic second-order logic
- Computing and listing \(st\)-paths in public transportation networks
- Output-polynomial enumeration on graphs of bounded (local) linear MIM-width
- Reverse search for enumeration
- Not all FPRASs are equal: demystifying FPRASs for DNF-counting
- Efficient algorithms for dualizing large-scale hypergraphs
- Parametrized complexity theory.
- A new algorithm for optimal 2-constraint satisfaction and its implications
- Enumeration Complexity of Logical Query Problems with Second-order Variables
- Constant Time Enumeration by Amortization
- Enumeration of the Monomials of a Polynomial and Related Complexity Classes
- MSO Queries on Tree Decomposable Structures Are Computable with Linear Delay
- Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
- Generating Linear Extensions Fast
- On generating all solutions of generalized satisfiability problems
- Constant Time Generation of Free Trees
This page was built for publication: Enumerating models of DNF faster: breaking the dependency on the formula size
