welcome: please sign in
location: Diff for "FinalProblemDescriptions/Tomography"
Differences between revisions 4 and 5
⇤ ← Revision 4 as of 2011-01-19 16:30:42 →
Size: 1460
Editor: CarmenSantoro
Comment:
← Revision 5 as of 2011-01-20 12:16:43 → ⇥
Size: 1502
Editor: CarmenSantoro
Comment:
Deletions are marked like this. Additions are marked like this.
Line 4: Line 4:

== Predicates ==

 * '''Input''': max_node_num/1, max_traceroute_num/1, traceroute/2

 * '''Output''': sol/1
Line 15: 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 19: 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 21: 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) ==

Tomography (Graph set covering)

Contents

  1. Tomography (Graph set covering)
    1. Problem Description
    2. Predicates
    3. Input format
    4. Output format
    5. Example(s)
    6. Author(s)

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)

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

ASP Competition 2011: FinalProblemDescriptions/Tomography (last edited 2011-02-02 19:04:41 by MarioAlviano)