Real-time minimum vertex cover for two-terminal series-parallel graphs
Marius Nagy, Selim G. Akl · International Journal of High Performance Computing and Networking · 2006
In this paper we show how the tree contraction method can be applied to compute the cardinality of the minimum vertex cover of a two-terminal series-parallel graph. We then construct a real-time paradigm for this problem and show that in the new computational environment, a parallel algorithm is superior to the best possible sequential algorithm, in terms of the accuracy of the solution computed. Specifically, there are cases in which the solution produced by a parallel algorithm that uses p processors is better than the output of any sequential algorithm for the same problem, by a factor superlinear in p.