Class Tree
Description Let G be a *directed* graph. A spanning tree is d-bounded if for every
vertex the number of outgoing edges at this vertex is at most d.

In the bounded spanning tree problem we are given a directed graph
G=(V,E), where V is the set of vertices and E is the set of edges.
We are also given a bound d.

The goal is to find a d-bounded spanning tree in G.

Input Format
============
Input data are stored in a plain text file. The
format of the file is as follows:
a. The file starts with n lines that define the number of vertices in
the problem using predicate "vtx" as follows.
vtx(1).
vtx(2).
...
vtx(n).

b. The file then specifies the edges of the graph using predicate "edge".
Each line is of the form "edge(i,j)" meaning that there is a directed
edge from vertex i to vertex j.

c. Then there is the single line:
bound(d).

Example input:
vtx(1).
vtx(2).
vtx(3).
vtx(4).
edge(1,2).
edge(2,3).
edge(2,4).
edge(3,4).
edge(1,4).
bound(1).

Output Requirement
==================
The solution must be encoded by a binary predicate "bstedge", where
"bstedge(i,j)" stands for: "edge(i,j) of G is in the bounded spanning
tree".

For the input given above, the following is a 1-bounded spanning
tree:

bstedge(1,2) bstedge(2,3) bstedge(3,4)

The corresponding answer set produced by a solver must contain exactly
these ground atoms of the form "bstedge" (and possibly some other atoms
based on other predicates).

For the same input, the following *is not* a 1-bounded spanning
tree (even though it is a spanning tree):

bstedge(1,2) bstedge(2,3) bstedge(2,4)

Authors: Gayathri Namasivayam and Miroslaw Truszczynski
Affiliation: University of Kentucky
Email: {gayathri, mirek}@cs.uky.edu
Encodings
1 - 7 of 7