welcome: please sign in

Upload page content

You can upload content for the page named below. If you change the page name, you can also upload content for another page. If the page name is empty, we derive the page name from the file name.

File to load page content from
Page name
Comment

location: FinalProblemDescriptions / Tomography

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