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

DOI10.1007/bfb0030837zbMath1527.68049OpenAlexW2170207422MaRDI QIDQ6085711

Seiichiro Tani, Kazuyoshi Hayase, Kunihiko Sadakane

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

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

Related Items

ZDD-based algorithmic framework for solving shortest reconfiguration problems

Cites Work

• On generating all maximal independent sets
• Graph-Based Algorithms for Boolean Function Manipulation
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• A New Algorithm for Generating All the Maximal Independent Sets
• Unnamed Item
• Unnamed Item