welcome: please sign in
location: Diff for "FinalProblemDescriptions/Tomography"
Differences between revisions 1 and 6 (spanning 5 versions)
⇤ ← Revision 1 as of 2011-01-18 13:34:39 →
Size: 20
Editor: CarmenSantoro
Comment:
← Revision 6 as of 2011-02-02 19:04:16 → ⇥
Size: 1702
Editor: MarioAlviano
Comment:
Deletions are marked like this. Additions are marked like this.
Line 1: Line 1:
Under construction = Tomography (Graph set covering) =

<<TableOfContents>>

== 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

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)

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

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