Minimum Spanning Tree Problem
I am interested in developing a practical application with regard to finding minimum spanning tree. Say one has an un-directed graph that has weighted edges. The goal would be to find the minimum spanning tree that connects all points on the graph with the lowest weight. How would this problem be mapped to a D Wave computer?
Comments
Hello,
There are a number of ways that you could map this problem to the QPU.
You could try using CSPs (Constraint Satisfaction Problems):
https://docs.ocean.dwavesys.com/projects/binarycsp/en/latest/intro.html
This problem sounds similar to the Map Colouring problem.
Here is a link to a step by step explanation of how this problem was formulated for the QPU:
https://docs.ocean.dwavesys.com/en/latest/examples/map_coloring.html
I can imagine some kind of constraint to allow only one path between layers of the tree structure would be similar to one colour per province.
This also sounds very similar to the TSP (Traveling Sales Person) problem in which the paths between cities are weighted:
https://docs.ocean.dwavesys.com/projects/dwave-networkx/en/latest/reference/algorithms/tsp.html
There was also a post about the TSP problem with some interesting information:
https://support.dwavesys.com/hc/en-us/community/posts/360028972434
I hope this was helpful.
Please feel free to reach out with any additional questions.
Please sign in to leave a comment.