Output-size sensitiveness of OBDD construction through maximal independent set problem

DOI10.1007/BFB0030837MaRDI QIDQ6085711zbMATH OpenOpenAlexFDO

Authors Kazuyoshi Hayase, Kunihiko Sadakane, Seiichiro Tani

Publication date 12 December 2023

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

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

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Boolean functions (06E30) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On the size of (generalized) OBDDs for threshold functions
• scientific article; zbMATH DE number 1500659
• Least upper bounds for the size of OBDDs using symmetry properties
• Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems
• scientific article; zbMATH DE number 1670823
• On the hardness of approximating the minimum consistent OBDD problem
• scientific article; zbMATH DE number 1088264
• On the evolution of the worst-case OBDD size
• The nonapproximability of OBDD minimization
• Least upper bounds on OBDD sizes

Cites work

• A New Algorithm for Generating All the Maximal Independent Sets
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• Graph-Based Algorithms for Boolean Function Manipulation
• scientific article; zbMATH DE number 1555978 (Why is no real title available?)
• scientific article; zbMATH DE number 910866 (Why is no real title available?)
• On generating all maximal independent sets

Cited in

(1)

• ZDD-based algorithmic framework for solving shortest reconfiguration problems

This page was built for publication: Output-size sensitiveness of OBDD construction through maximal independent set problem

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