Package com.jgalgo.alg.cover

Interface DominatingSetAlgo

All Known Implementing Classes:
DominatingSetAlgoAbstract, DominatingSetAlgoGreedy
public interface DominatingSetAlgo
An algorithm for computing a minimum dominating set.

Given a graph \(G = (V, E)\), a dominating set is a subset \(D \subseteq V\) such that for every \(v \in V\), either \(v \in D\) or there is an edge \((u, v) \in E\) such that \(u \in D\). The minimum dominating set problem is to find a dominating set of minimum size or weight. The problem is NP-hard. Algorithms implementing this interfaces are heuristics or fixed ration approximation algorithms.

In a directed graph, the 'dominance' should be defined with respect to either the in-edges, out-edges or in-edges + out-edges of the vertices. This is specified as a EdgeDirection parameter to computeMinimumDominationSet(Graph, WeightFunction, EdgeDirection), which yields different types of dominating sets.

Use newInstance() to get a default implementation of this interface.

Author:
Barak Ugav

  • Method Details

    • computeMinimumDominationSet

      default <V, E> Set<V> computeMinimumDominationSet(Graph<V,E> g, WeightFunction<V> w)
      Compute a minimum dominating set of the graph with respect to the in-degree + out-degree of the vertices.
      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - a graph
      w - a vertex weight function
      Returns:
      a minimum dominating set of the graph

    • computeMinimumDominationSet

      <V, E> Set<V> computeMinimumDominationSet(Graph<V,E> g, WeightFunction<V> w, EdgeDirection dominanceDirection)
      Compute a minimum dominating set of the graph with respect to the given edges direction.
      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - a graph
      w - a vertex weight function
      dominanceDirection - the direction of the edges to consider
      Returns:
      a minimum dominating set of the graph

    • isDominatingSet

      static <V, E> boolean isDominatingSet(Graph<V,E> g, Collection<V> dominatingSet, EdgeDirection dominanceDirection)
      Check whether a given set of vertices is a dominating set of a graph.
      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - a graph
      dominatingSet - a set of vertices
      dominanceDirection - the direction of the edges to consider, if null then EdgeDirection.All is used
      Returns:
      true if the given set is a dominating set of the graph

    • newInstance

      static DominatingSetAlgo newInstance()
      Create a new dominating set algorithm object.

      This is the recommended way to instantiate a new DominatingSetAlgo object.

      Returns:
      a default implementation of DominatingSetAlgo