Conference proceeding
A practical method for computing vertex covers for large graphs
1992 IEEE International Symposium on Circuits and Systems (ISCAS), Vol.4, pp.1859-1862 vol.1
1992
DOI: 10.1109/ISCAS.1992.230450
Abstract
The authors present a new heuristic solution technique for the vertex cover problem. This technique is computationally efficient for very large graphs containing thousands of vertices and edges. It is based upon a general heuristic problem solving framework known as parallel dynamic interaction (PDI). A novel aspect of PDI is that it employs an inherently parallel computational structure that is easily implementable on shared memory multiprocessors of modest size. Empirical data indicate that PDI consistently outperforms other reported vertex cover heuristics, including those that require orders of magnitude greater execution time.< >
Details
- Title: Subtitle
- A practical method for computing vertex covers for large graphs
- Creators
- I Pramanick - University of AlabamaJ.G Kuhl - University of Iowa
- Resource Type
- Conference proceeding
- Publication Details
- 1992 IEEE International Symposium on Circuits and Systems (ISCAS), Vol.4, pp.1859-1862 vol.1
- Publisher
- IEEE
- DOI
- 10.1109/ISCAS.1992.230450
- ISSN
- 0271-4310
- Language
- English
- Date published
- 1992
- Academic Unit
- Electrical and Computer Engineering; Public Policy Center (Archive)
- Record Identifier
- 9984283580302771
Metrics
27 Record Views