On the Hardness of Energy Minimisation for Crystal Structure Prediction

DOI10.1007/978-3-030-38919-2_48zbMath1440.82010arXiv1910.12026OpenAlexW3004044864MaRDI QIDQ3297788

Igor Potapov, Duncan Adamson, Argyrios Deligkas, Vladimir V. Gusev

Publication date: 20 July 2020

Published in: SOFSEM 2020: Theory and Practice of Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Applications of graph theory (05C90) Statistical mechanics of crystals (82D25) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Signed and weighted graphs (05C22)

Related Items (3)

The k-centre problem for classes of cyclic words ⋮ Hardness results for multimarginal optimal transport problems ⋮ On the Hardness of Energy Minimisation for Crystal Structure Prediction*

Cites Work

• NP-hardness of the Euclidean Max-Cut problem
• How to predict very large and complex crystal structures
• Unit disk graphs
• A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation
• The Planar k-Means Problem is NP-Hard
• Node-Deletion NP-Complete Problems
• Node-Deletion Problems on Bipartite Graphs
• Node-and edge-deletion NP-complete problems

This page was built for publication: On the Hardness of Energy Minimisation for Crystal Structure Prediction