1. Real-time minimum vertex cover for two-terminal series-parallel graphs
- Author
-
Nagy, Marius and Akl, Selim G.
- Subjects
Algorithms -- Usage ,Trees (Graph theory) -- Usage ,Algorithm ,Computers and office automation industries - Abstract
Byline: Marius Nagy, Selim G. Akl 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.
- Published
- 2007