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 Summary

Modifier and Type	Method	Description
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.
<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.
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.
static DominatingSetAlgo	newInstance()	Create a new dominating set algorithm object.

Method Detail

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