Fast Self-Reduction Algorithms for Combinatorical Problems of VLSI-Design

摘要: In a recent series of papers [FL1, FL2, FL3], we have proven the existence decision algorithms with low-degree polynomial running times for number well-studied VLSI layout, placement and routing problems. These results make use powerful Robertson-Seymour theorems on well-partial-ordering graphs under both minor immersion orders. present paper, study complexity construction versions these problems, focusing efficient self-reduction strategies. We introduce notion fast in this setting develop general technique, which term scaffolding, that is useful design algorithms.