Date Added: May 2009
Duality plays a significant role in optimization theory, particularly in discrete optimization on graphs and networks. Circuits and cuts in graphs are dual concepts. Similarly, deletion and contraction of an edge are dual graph operations. Most often, for a primal algorithm based on circuits there is a dual algorithm based on cuts for the same problem. The primal and dual algorithms possess certain characteristics that make one superior to the other depending on the application. The SMART algorithm for the survivable logical topology design problem is based on circuits. This is a novel and very significant contribution to the problem. The question then arises whether there exists a dual methodology based on cuts.