METHOD AND SYSTEM FOR DETERMINING A MINIMUM CONNECTED DOMINATING SET IN A GRAPH

摘要

A method and a system are disclosed for determining a minimum connecteddominating set in a graph, the method comprising obtaining an indication of aninputgraph, the input graph comprising a plurality of nodes and a plurality ofedges;generating a distance table comprising for each given node of the input graph,anindication of a distance between the given node and each of the other node oftheplurality of nodes; generating a corresponding constrained binary quadraticprogramming problem using the generated distance table; providing thecorresponding constrained binary quadratic programming problem to a solver,wherein the solver is one of a quadratic unconstrained binary optimizationsolver anda quadratic constrained binary optimization solver; obtaining at least oneapproximate solution from the solver; and providing the at least oneapproximatesolution, wherein the providing comprises post-processing the at least oneapproximate solution if the at least one approximate solution does notcomprise aconnected dominating set without redundant nodes.