Method and system for solving a minimum connected dominating set problem using quantum annealing for distance optimization

摘要

A method is disclosed for determining a minimum connected dominating set in a graph, the method comprising obtaining an indication of an input graph, the input graph comprising a plurality of nodes and a plurality of edges; generating a distance table comprising for each node of the input graph, an indication of a distance between the given node and each of the other node of the plurality of nodes; generating a corresponding constrained binary quadratic programming problem using the generated distance table; providing the corresponding constrained binary quadratic programming problem to a quantum annealing solver; obtaining at least one approximate solution from the quantum annealing solver; post-processing the at least one approximate solution and providing the post-processed at least one approximate solution.