Title: Real-time minimum vertex cover for two-terminal series-parallel graphs

Authors: Marius Nagy, Selim G. Akl

Addresses: School of Computing, Queen's University, Kingston, Ontario, K7L 3N6 Canada. ' School of Computing, Queen's University, Kingston, Ontario, K7L 3N6 Canada.

Abstract: 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.

Keywords: recursive graphs; decomposition tree; minimum vertex cover; series-parallel graphs; tree contraction; parallel algorithms; real-time; accuracy ratio; high performance computing.

DOI: 10.1504/IJHPCN.2006.013490

International Journal of High Performance Computing and Networking, 2006 Vol.4 No.5/6, pp.347 - 356

Published online: 01 May 2007 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article