zbMATH — the first resource for mathematics

Fast self-reduction algorithms for combinatorial problems of VLSI design. (English) Zbl 0652.68048
VLSI algorithms and architectures, Proc. 3rd Aegean Workshop Comput., Corfu/Greece 1988, Lect. Notes Comput. Sci. 319, 278-287 (1988).
Summary: [For the entire collection see Zbl 0643.00025.]
In a recent series of papers [Inf. Process. Lett. 26, 157-162 (1987; Zbl 0637.68053); J. Assoc. Comput. Mach. 35, No.3, 727-739 (1988; see the following review)], we have proven the existence of decision algorithms with low-degree polynomial running times for a number of well-studied VLSI layout, placement and routing problems. These results make use of the powerful Robertson-Seymour theorems on the well-partial-ordering of graphs under both the minor and immersion orders. In the present paper, we study the complexity of construction versions of these problems, focusing on efficient self-reduction strategies. We introduce a notion of fast self-reduction in this setting and develop a general technique, which we term scaffolding, that is useful in the design of fast self- reduction algorithms.

68Q25 Analysis of algorithms and problem complexity
68R99 Discrete mathematics in relation to computer science
68R10 Graph theory (including graph drawing) in computer science