A non-transitory computer-readable storage medium for storing computer-executable instructions which, when executed, cause a digital computer to perform a method 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.