ZDD-based algorithmic framework for solving shortest reconfiguration problems

DOI10.1007/978-3-031-33271-5_12arXiv2207.13959OpenAlexW4377249480MaRDI QIDQ6057258

Takahisa Toda, Jun Kawahara, Takehiro Ito, Yu Nakahata, Junichi Teruyama, Takehide Soh, Akira Suzuki

Publication date: 4 October 2023

Published in: Integration of Constraint Programming, Artificial Intelligence, and Operations Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2207.13959

zbMATH Keywords

graph algorithmsbinary decision diagramscombinatorial reconfiguration

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Operations research and management science (90Bxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Complexity of independent set reconfigurability problems
• On the complexity of reconfiguration problems
• Implicit enumeration of topological-minor-embeddings and its application to planar subgraph enumeration
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Distributed reconfiguration of maximal independent sets
• Introduction to reconfiguration
• Connectedness of the graph of vertex-colourings
• The complexity of change
• Graph-Based Algorithms for Boolean Function Manipulation
• Decision Diagrams for Discrete Optimization: A Survey of Recent Advances
• Output-size sensitiveness of OBDD construction through maximal independent set problem
• Reconfiguration of connected graph partitions

This page was built for publication: ZDD-based algorithmic framework for solving shortest reconfiguration problems