A moderately exponential time algorithm for \(k\)-IBDD satisfiability

DOI10.1007/s00453-017-0332-2zbMath1391.68101OpenAlexW2677509542WikidataQ115606758 ScholiaQ115606758MaRDI QIDQ722517

Junichi Teruyama, Atsuki Nagao, Kazuhisa Seto

Publication date: 26 July 2018

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-017-0332-2

zbMATH Keywords

satisfiabilityindexed binary decision diagrammoderately exponential timeordered binary decision diagram

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (1)

Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression

Cites Work

• Unnamed Item
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Mining circuit lower bound proofs for meta-algorithms
• Improving Exhaustive Search Implies Superpolynomial Lower Bounds
• Nonuniform ACC Circuit Lower Bounds
• Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms
• Graph-Based Algorithms for Boolean Function Manipulation
• Branching Programs and Binary Decision Diagrams
• An algorithm for the satisfiability problem of formulas in conjunctive normal form
• Algorithms and Computation
• STACS 2004

This page was built for publication: A moderately exponential time algorithm for \(k\)-IBDD satisfiability