» ASP Competition | |
|
Connected Dominating SetProblem descriptionA connected dominating set in an undirected graph G=(V,E), where V is a set of vertices, and E is a set of edges, is a subset D of vertices in the graph such that the following two conditions hold:
Input formatInput graphs are stored in plain text files, one file for each graph. The format of the file is as follows:
Output formatThe programmers must ensure that, in the answer-sets, predicate "dom" is used to represent the dominating set found by their solvers. Predicate dom takes one parameter: dom(x), which means that the vertex x is in the connected dominating set of size at most the specified bound. ExampleInput: vtx(1). vtx(2). vtx(3). vtx(4). vtx(5). vtx(6). vtx(7). vtx(8). edge(8,5). edge(7,4). edge(8,7). edge(7,5). edge(6,7). edge(8,1). edge(3,4). edge(6,1). edge(6,2). edge(3,5). edge(1,5). edge(5,4). edge(3,7). edge(5,2). edge(2,8). edge(3,1). edge(7,1). edge(6,4). edge(4,2). edge(8,4). bound(3). Graphical representation of the given graph: Valid Output: dom(7). dom(8). The vertices in the dominating set is shown within the rectangle:
Authors: Gayathri Namasivayam and Miroslaw Truszczynski |