longest chain! is that a DFS?
- To: mathgroup at smc.vnet.net
- Subject: [mg78780] longest chain! is that a DFS?
- From: mumat <csarami at gmail.com>
- Date: Mon, 9 Jul 2007 01:40:28 -0400 (EDT)
Hi there Everyone,
Here is my question.
Assume S is the set {B1,B2,...,Bn} where Bi's are non-empty sets of
ordered pairs of A={1,2,3,...,8} ( <--- for simplicity).
our goal is to list all sequences of the form
X_1,X2,X3,X_4,...,X_m over A
of m, the longest possible length for which
for every i: (X_i, X_(i+1)) is in B_i AND (X_(i+1),X_(i
+2)) is in B_(i+1).
For instance, ( with Notation: ab:={a,b})
S={ {12,23,24,56}, {14,28,45,67},{81,15,78}, {56,85} }, so
B1={12,23,24,56},B2={14,28,45,67},B3={81,85,78},B4={52,85}.
seq: 1,2,8,5,2 is of longest possible length 5.
2,4,8,5,2 is another sequence of longest length.
Any help would be greatly appreciated.
Best regards,
chekad sarami