Characteristics of the maximal independent set ZDD

DOI10.1007/S10878-014-9722-4MaRDI QIDQ405673zbMATH OpenOpenAlexFDO

Authors David R. Morrison, E. C. Sewell, Sheldon H. Jacobson

Publication date 5 September 2014

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-014-9722-4

zbMATH Keywords

graph theoryindependent setsbinary decision diagrams

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Recommendations

• Storing set families more compactly with top ZDDs
• Zero-suppression and computation models
• Zero-suppressed BDDs and their applications
• DenseZDD: a compact and fast index for families of sets
• Extracting co-occurrence relations from ZDDs

Cites work

• scientific article; zbMATH DE number 3353170 (Why is no real title available?)
• scientific article; zbMATH DE number 956839 (Why is no real title available?)
• 0/1 vertex and facet enumeration with BDDs
• Algorithm 457: finding all cliques of an undirected graph
• Binary Decision Diagrams
• Graph-Based Algorithms for Boolean Function Manipulation
• Improving the variable ordering of OBDDs is NP-complete
• Maximum-weight stable sets and safe lower bounds for graph coloring
• On Threshold BDDs and the Optimal Variable Ordering Problem
• Optimization Bounds from Binary Decision Diagrams
• Solving the pricing problem in a branch-and-price algorithm for graph coloring using zero-suppressed binary decision diagrams
• The worst-case time complexity for generating all maximal cliques and computational experiments
• Zero-suppressed BDDs and their applications

Cited in

(7)

• Finding all solutions and instances of Numberlink and Slitherlink by ZDDs
• Solving the pricing problem in a branch-and-price algorithm for graph coloring using zero-suppressed binary decision diagrams
• Enumerating all subgraphs under given constraints using zero-suppressed sentential decision diagrams
• DenseZDD: a compact and fast index for families of sets
• Extracting co-occurrence relations from ZDDs
• Zero-suppression and computation models
• Zero-suppressed BDDs and their applications

Describes a project that uses

Uses Software

• DIMACS
• Algorithm 457

This page was built for publication: Characteristics of the maximal independent set ZDD

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