Revision as of 00:12, 13 July 2012 edit BIOalgorithm (talk \| contribs) 6 edits No edit summary ← Previous edit		Revision as of 00:52, 13 July 2012 edit undo BIOalgorithm (talk \| contribs) 6 edits No edit summary Next edit →
Line 99: * Test each S-prime component to see if it is an interval graph. :This can be done by truly building the ~~true~~corresponding interval graph; first adding the non-simplicial vertices, then adding the simplicial vertices through a linear scan. The second part is intuitive; the first part needs more detailed discussion. '''Lemma''' Let u<sub>k</sub> be the next interval to be placed, which is not a neighbor of previously chosen intervals. Let u<sub>j</sub> be the parent of u<sub>k</sub> and u<sub>i</sub> be the parent of u<sub>j</sub> in the BFS-tree. It can be determined uniquely which endpoints of u<sub>j</sub> or u<sub>i</sub> is contained in u<sub>k</sub>. There are three cases, place each edge according to its category. Case 1: (f(u<sub>i</sub>), u<sub>j</sub>) ∉ E. If u<sub>i</sub> ,u<sub>k</sub> are on the different side of u<sub>j</sub>, u<sub>k</sub> would contain u<sub>j</sub>. Case 2: (f(u<sub>k</sub>), u<sub>j</sub> ) ∉ E. Again, if u<sub>i</sub>, u<sub>k</sub> are on the different side of u<sub>j</sub>, u<sub>k</sub> would contain u<sub>j</sub>. Case 3: (f(u<sub>j</sub>), u<sub>k</sub>) ∉ E and (f(u<sub>j</sub>), u<sub>i</sub>) ∉ E. If u<sub>i</sub> ,u<sub>k</sub> are on the different sides of u<sub>j</sub>, u<sub>k</sub> cannot be adjacent to u<sub>i</sub>. ::(''f''(''u'') := ''u'''s neighbor vertex with the smallest ''π''-index.) ==Related families of graphs==

User:BIOalgorithm/sandbox: Difference between revisions