Du
Naive algorithm
newedgdes(C,p,q,r,s):
return { (C[p-1],C[q+1]), (C[q],C[s]), (C[p], C[r]) }
countbps(E,NE):
newbps = 0
for ( ne in NE )
if ( ne !in E )
++newbps
return newbps
countmainbps(F,E,NE):
newmainbps = 0
for ( ne in NE )
if ( ne !in E && ne in F )
++newmainbps
return newmainbps
m(C,F,E,p):
min = infinity
n = |C|
for ( q in range(p,p-2) )
for ( s in range( q + 2, p ) )
r = s - 1
for ( i in range(2) )
NE = newedges(C,p,q,r,s)
if ( |NE| != 0 )
newbps = countbps(F,E,NE)
newmainbps = countmainbps(F,E,NE)
if ( newbps == 0 || newmainbps > 0 )
min = newbps < min ? newbps : min
swap(r,s)
return min
Better algorithm
As we iterate over the different possible values for , there are incrementally more possibilities for . Each selection of implies a possible breakpoint for .
For each q, for all the valid (r,s) for that q, will track those that result in no breakpoint for (p,r).
will track those s, valid with q, that result in a breakpoint (p,r) that is a former breakpoint.
will track those s, valid with q, that result in a breakpoint (p,r) that are not a former breakpoint.
is a set that contains the adjacent vertices to in G.
is a set that contains those adjacent vertices to in G, which don't form a breakpoint in F, the set of former main breakpoints. In other words, all v, where .