Tomorgraphy (Graph set covering)
Contents
Problem Description
* Input Predicates: max_node_num/1, max_traceroute_num/1, traceroute/2
* Output Predicates: sol/1
In order to guarantee the quality of communication of a PC network, the network administrator routinely sends out probing messages from the servers to the network. Each probing message is sent to a subset of nodes known as a trace route. Given a set of trace routes of past probing messages, the problem is to find a smallest subset of trace routes that can cover the entire network.
In the input, the max_node_num(N) gives the number of nodes in the network (nodes are numbered from 1 to N), the fact max_traceroute_num(M) gives the number of trace routes M (trace outes are numbered from 1 to M), and the predicate traceroute/2 gives the set of trace routes, where a fact traceroute(I,Node) means that the node Node is included in the trace route numbered I. The predicate sol/1 gives the set of selected trace routes that covers the entire network, where a fact sol(I) means that the trace route numbered I is selected.
Input format
Output format
Example
Author(s)
- Atsuo Tachibana
- KDD Labs, Japan
- Neng-Fa Zhou
- CUNY Brooklyn College and Graduate Center, USA
- Masato Tsuru
- Kyushu Institute of Technology, Japan