# Instance Class WeightedSpanningTree

Class Tree [Root]    Unclassified (3031) Let G be a *directed* graph. Let every edge in the graph be assigned a weight. A spanning tree is w-bounded if for every vertex the sum of the weights of the outgoing edges at this vertex is atmost w. In the weighted spanning tree problem we are given a directed graph G=(V,E,W), where V is the set of vertices, E is the set of edges and W is a function that maps each edge in the graph to an integer weight from the range 1..|V|. We are also given an integer bound w. The goal is to find a w-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 are as many lines as there are edges in the graph of the form Weight wtedge(i,j)=v. c. Then there is the single line bound(w). 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). Weight wtedge(1,2)=1. Weight wtedge(2,3)=2. Weight wtedge(2,4)=1. Weight wtedge(3,4)=2. Weight wtedge(1,4)=1. bound(2). Output Requirement ================== The solution must be encoded by a binary predicate "wstedge", where "wstedge(i,j)" stands for: "there is an edge(i,j) in the weighted spanning tree". For the input given above, the following is a 2-weighted spanning tree: wstedge(1,2) wstedge(2,3) wstedge(3,4) The corresponding answer set produced by a solver must contain exactly these ground atoms of the form "wstedge" (and possibly some other atoms based on other predicates). For the same input, the following *is not* a 2-weighted spanning tree: wstesge(1,2) wstedge(2,3) wstedge(2,4) Authors: Gayathri Namasivayam and Miroslaw Truszczynski Affiliation: University of Kentucky Email: {gayathri, mirek}@cs.uky.edu Martin Gebser 201_rand_30_140_1147035578_0     201_rand_30_140_1147043744_0     205_rand_32_140_1344634881_0     205_rand_32_140_1344639651_0     205_rand_32_140_1344655193_0     205_rand_32_140_1344664746_0     206_rand_32_145_1872922024_0     206_rand_32_145_1872923239_0     206_rand_32_145_1872925756_0     206_rand_32_145_1872927471_0     206_rand_32_145_1872928606_0     206_rand_32_145_1872928657_0     206_rand_32_145_1872937399_0     206_rand_32_145_1872937623_0     206_rand_32_145_1872946789_0     206_rand_32_145_1872947197_0     206_rand_32_145_1872948178_0     206_rand_32_145_1872949941_0     206_rand_32_145_1872951076_0     207_rand_35_138_2077101081_0    un-/mark all