» ASP Competition | |
|
Weight-Bounded Dominating SetProblem descriptionThe Weight-Bounded Dominating Set problem deals with directed graphs G = (V,E), where V is the set of vertices and E the set of edges, such that every edge (i,j) in E is associated with a weight w_(i,j). Furthermore, we consider a certain cardinality k and a minimum weight w. The problem is to find a subset D of V such that |D| ≤ k and, for each vertex v in V, at least one of the following conditions holds:
Input formatAn input consists of the following parts: a.
The vertices of the input graph are numbered and given by instances of "vtx" as follows: b.
The edges of the graph are given by instances of "edge" as follows: c.
For each edge(i_1,i_2),
there is exactly one instance of "edgewt"
providing the edge's (positive) weight w_i: d.
There is exactly one instance of "minweight"
specifying the minimum combined weight w
of a vertex' predecessors or successors
needed to dominate the vertex: e.
Finally, there is exactly one instance of predicate "bound"
specifying the maximum cardinality k of a weight-bounded dominating set D: For further illustration, compare the instances available at asparagus. Output formatA solution is represented by means of a unary predicate "in" such that there are at most k instances of "in". The set D of vertices for which "in" holds must be a weight-bounded dominating set for the input graph. Author: Lengning Liu, Miroslaw Truszczynski, and Martin Gebser |