Characteristics of the maximal independent set ZDD

DOI10.1007/S10878-014-9722-4zbMATH Open1302.90188OpenAlexW2074844633MaRDI QIDQ405673FDOQ405673

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On Threshold BDDs and the Optimal Variable Ordering Problem
• Algorithm 457: finding all cliques of an undirected graph
• Graph-Based Algorithms for Boolean Function Manipulation
• Maximum-weight stable sets and safe lower bounds for graph coloring
• Binary Decision Diagrams
• Zero-suppressed BDDs and their applications
• Improving the variable ordering of OBDDs is NP-complete
• The worst-case time complexity for generating all maximal cliques and computational experiments
• 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
• 0/1 vertex and facet enumeration with BDDs

Cited In (2)

• 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

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)