welcome: please sign in
location: attachment:maximal-monochrome-paths-description.txt of EncodingsExamples

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.