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 that result in a breakpoint that is a former main breakpoint.