Enumerating all subgraphs under given constraints using zero-suppressed sentential decision diagrams

DOI10.4230/LIPICS.SEA.2020.9zbMATH Open1515.68251MaRDI QIDQ6487604FDOQ6487604

Authors: Yu Nakahata, Masaaki Nishino, Jun Kawahara, Shin-Ichi Minato 

Publication date: 7 February 2023

Recommendations

• Zero-suppressed BDDs and their applications
• Enumerating graph partitions without too small connected components using zero-suppressed binary and ternary decision diagrams
• Characteristics of the maximal independent set ZDD
• Storing set families more compactly with top ZDDs
• Zero-suppression and computation models

zbMATH Keywords

decision diagramsubgraph enumerationtop-down construction algorithmzero-suppressed sentential decision diagram

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Nonnumerical algorithms (68W05) Enumeration in graph theory (05C30)

Cited In (2)

• Fast enumeration of all cost-bounded solutions for combinatorial problems using ZDDs
• Enumerating graph partitions without too small connected components using zero-suppressed binary and ternary decision diagrams

This page was built for publication: Enumerating all subgraphs under given constraints using zero-suppressed sentential decision diagrams

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