|
Size: 1388
Comment:
|
← Revision 7 as of 2011-02-02 19:04:41 ⇥
Size: 1702
Comment: Mi ha cancellato la pagina!
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 1: | Line 1: |
| = Tomorgraphy (Graph set covering) = | = Tomography (Graph set covering) = |
| Line 7: | Line 7: |
| * Input Predicates: max_node_num/1, max_traceroute_num/1, traceroute/2 * Output Predicates: sol/1 |
|
| Line 13: | Line 9: |
| 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. | == Predicates == * '''Input''': {{{max_node_num/1, max_traceroute_num/1, traceroute/2}}} * '''Output''': {{{sol/1}}} |
| Line 17: | Line 17: |
| 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. |
|
| Line 19: | Line 21: |
| == Example == | 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. == Example(s) == Input: {{{max_node_num(3). max_traceroute_num(3). traceroute(1,1). traceroute(1,2). traceroute(2,2). traceroute(2,3). traceroute(3,1). traceroute(3,2).}}} Possible output: {{{sol(1). sol(2).}}} |
| Line 22: | Line 30: |
* Atsuo Tachibana * KDD Labs, Japan * Neng-Fa Zhou * CUNY Brooklyn College and Graduate Center, USA * Masato Tsuru * Kyushu Institute of Technology, Japan |
* Author: Atsuo Tachibana * Affiliation: KDD Labs, Japan * Author: Neng-Fa Zhou * Affiliation: CUNY Brooklyn College and Graduate Center, USA * Author: Masato Tsuru * Affiliation: Kyushu Institute of Technology, Japan |
Tomography (Graph set covering)
Contents
Problem Description
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.
Predicates
Input: max_node_num/1, max_traceroute_num/1, traceroute/2
Output: sol/1
Input format
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.
Output format
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.
Example(s)
Input: max_node_num(3). max_traceroute_num(3). traceroute(1,1). traceroute(1,2). traceroute(2,2). traceroute(2,3). traceroute(3,1). traceroute(3,2).
Possible output: sol(1). sol(2).
Author(s)
- Author: Atsuo Tachibana
- Affiliation: KDD Labs, Japan
- Author: Neng-Fa Zhou
- Affiliation: CUNY Brooklyn College and Graduate Center, USA
- Author: Masato Tsuru
- Affiliation: Kyushu Institute of Technology, Japan