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

DOI10.4230/LIPICS.SEA.2020.9MaRDI QIDQ6487604zbMATH OpenFDO

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

Publication date 7 February 2023

Full work available at URL https://doi.org/10.4230/LIPICS.SEA.2020.9

zbMATH Keywords

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

Mathematics Subject Classification ID

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

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

Cited in

(3)

• Enumerating graph partitions without too small connected components using zero-suppressed binary and ternary decision diagrams
• Fast enumeration of all cost-bounded solutions for combinatorial problems using ZDDs
• Exact counting of subtrees with diameter no more than d in trees: a generating function approach

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)