# Instance Class BoundedSpanningTree

Class Tree 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 Martin Gebser 104_rand_45_250_1727037601_0     104_rand_45_250_1727038210_0     104_rand_45_250_1727038633_0     104_rand_45_250_1727040059_0     104_rand_45_250_1727040917_0     104_rand_45_250_1727042043_0     104_rand_45_250_1727042720_0     104_rand_45_250_1727043336_0     104_rand_45_250_1727044175_0     104_rand_45_250_1727047830_0     104_rand_45_250_1727049295_0     104_rand_45_250_1727050284_0     104_rand_45_250_1727052928_0     104_rand_45_250_1727068226_0     104_rand_45_250_1727068712_0     122_rand_35_250_1700137086_0     122_rand_35_250_1700137636_0     122_rand_35_250_1700137959_0     122_rand_35_250_1700138097_0     122_rand_35_250_1700138738_0    un-/mark all