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 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