Class Tree  

Description 
Problem description ================ A (v,e,k)graph partition of an undirected weighted graph G=(V,E,W) where V is a set of vertices, E is a set of edges, and W is a weight function that assigns to each edge in the graph a nonnegative integer, is a collection of k disjoint sets of vertices such that the union of the sets in the collection is V and the following conditions hold: 1. the number of vertices in each set in the partition (i.e., block) is at least 1 and at most v, 2. for every pair of distinct blocks the sum of the weights of the edges between the blocks is at most e, and 3. the subgraph induced by the vertices in each of the blocks is connected. Input format ================ Input graphs are stored in plain text files, one file for each graph. The format of the file is as follows: 1. The file starts with lines that define vertices. Vertices are defined using predicate name "vtx". Vertices are represented as integers that always start from 1 and end at n, where n is the number of the vertices. 2. The definition of edges follows. The predicate name used to define edges is "edge". Predicate edge has two parameters. Intuitively, edge(x, y) means there is an undirected edge between x and y. 3. The weights assigned to each edge "edge(x, y)" are in the following lines by expressions "weight_ wtedge(x,y,w)” where w is a nonnegative integer. 4. Next line specifies the number of blocks in a partition, k. The predicate name is “parts”. Partitions are identified by integers that always start at 1 and end at k. 5. Next line provides a nonnegative integer bound v on the number of vertices in each partition. The predicate name is “vtxbound” 6. Finally, the predicate name that provides a nonnegative integer bound e on the total weight of edges between two blocks is “edgebound” Output format ================ The programmers must ensure that, in the answersets, predicate "partition" is used to represent the partition found by their solvers. Predicate partition takes two parameters: partition(x,z), which means that the vertex x is in the zth block. Example ================ Input: vtx(1). vtx(2). vtx(3). vtx(4). vtx(5). edge(4,5). edge(2,5). edge(2,3). edge(4,3). edge(4,2). edge(1,5). edge(1,4). edge(5,3). edge(1,2). edge(3,1). weight_wtedge(4,5,1). weight_wtedge(2,5,1). weight_wtedge(2,3,2). weight_wtedge(4,3,2). weight_wtedge(4,2,1). weight_wtedge(1,5,1). weight_wtedge(1,4,1). weight_wtedge(5,3,2). weight_wtedge(1,2,1). weight_wtedge(3,1,1). parts(1). parts(2). parts(3). vtxbound(3). edgebound(4). Valid Output: partition(1,1). partition(2,1). partition(3,1). partition(4,2). partition(5,3). Authors: Gayathri Namasivayam and Miroslaw Truszczynski Affiliation: University of Kentucky 
Encodings 1  1 of 1 
