Note on Problems which are Hard for some Weakly Connected Parallel Architectures
Abstract
In this paper the lower bound technique, based on information content, for special models of VLSI circuits defined by some topological restrictions is investigated. The assertion bounding possibilities of speeding up a VLSI computation by increasing the number of processors for circuits with f/separators is presented. Further possibilities of applying these results to obtain stronger lower bounds or proofs of noneffectivity of speeding up computation for some classes of problems and separators are shown.Downloads
Download data is not yet available.
Published
2012-03-05
How to Cite
Trenčanský, I. (2012). Note on Problems which are Hard for some Weakly Connected Parallel Architectures. Computing and Informatics, 15(5), 459–465. Retrieved from http://147.213.75.17/ojs/index.php/cai/article/view/686
Issue
Section
Articles