Attachment 'maximal-monochrome-paths-description.txt'
Download 1 Problem description
2 -------------------
3 Let G=<V,E> a directed graph, where each edge is given
4 a color. Does there exist a non-empty subset S of V that:
5
6 1. given any pair of vertex v1 and v2 n S, there is no
7 monochrome path between v1 and v2.
8 2. (maximality) for any vertex v not in S, there exists
9 a monochrome path connecting v to some other node in S.
10
11
12 Input format
13 ------------
14 A set of facts of the form
15 vertex(V). <-- vertices
16 edge(V1,V2,Color). <-- colored edges
17
18
19 Output format
20 -------------
21 a set of facts of the form
22 in(X). <-- selected nodes
23 if no instances of "in" are given, the answer is supposed
24 to be "NO".
Attached Files
You are not allowed to attach a file to this page.