Note on Problems which are Hard for some Weakly Connected Parallel Architectures

Authors

  • I. Trenčanský

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