A reducibility concept for problems defined in terms of ordered binary decision diagrams

DOI10.1007/BFB0023461MaRDI QIDQ5047173zbMATH OpenOpenAlexFDO

Authors Christoph Meinel, Anna Slobodová

Publication date 9 November 2022

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bfb0023461

Mathematics Subject Classification ID

Data structures (68P05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A reducibility concept for problems defined in terms of ordered binary decision diagrams
• On the minimization of (complete) ordered binary decision diagrams
• On the complexity of constructing optimal ordered binary decision diagrams
• A theoretical and numerical analysis of the worst-case size of reduced ordered binary decision diagrams
• Binary decision diagrams with edge-specified reductions
• Ordered binary decision diagrams and minimal trellises
• A rewriting approach to binary decision diagrams
• Ordered binary decision diagrams and the Davis-Putnam procedure
• Optimal ordered binary decision diagrams for read-once formulas
• Ordered binary decision diagrams, pigeonhole formulas and beyond

Cites work

• scientific article; zbMATH DE number 4047113 (Why is no real title available?)
• scientific article; zbMATH DE number 4072383 (Why is no real title available?)
• scientific article; zbMATH DE number 47903 (Why is no real title available?)
• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• Modified branching programs and their computational power
• Read-once projections and formal circuit verification with binary decision diagrams
• Reduction of OBDDs in linear time

Cited in

(2)

• A reducibility concept for problems defined in terms of ordered binary decision diagrams
• Chain reduction for binary and zero-suppressed decision diagrams

Describes a project that uses

Uses Software

• CUDD

This page was built for publication: A reducibility concept for problems defined in terms of ordered binary decision diagrams

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