Multi-Layer Channel Routing: Complexity and Algorithms, 1st Edition (Hardback) book cover

Multi-Layer Channel Routing

Complexity and Algorithms, 1st Edition

By R.K. Pal

Narosa

440 pages

Purchasing Options:$ = USD
Hardback: 9780849309311
pub: 2000-09-28
Currently out of stock
$110.00
x


FREE Standard Shipping!

Description

This book focuses on computation complexity and design of algorithms for multi-layer channel routing. In particular, it deals with various large-scale, computationally intensive optimization problems that have specific applications in many technology-supported routing models. The author includes numerous examples and exercises along with many hard-copy solutions that illustration the feasibility of different routing solutions. He also mentions several problems that remain open, pointing the way for future research.

Table of Contents

LITERATURE SURVEY

Terminology and Definitions

Two- and Three-Layer Routing is NP-Complete

Algorithms for Channel Routing

RESOLVING HORIZONTAL CONSTRAINTS IN

MULTI-LAYER CHANNEL ROUTING

Algorithms for Two-Layer Routing in the Absence of Vertical Constraints

Multi-Layer Vi+1Hi Channel Routing

A GENERAL FRAMEWORK FOR TRACK ASSIGNMENT IN MULTI-LAYER CHANNEL ROUTING

Formulation of the Problem and the Algorithm

Extensions of the TAH Framework to Other Problems

COMPUTATIONAL COMPLEXITY OF WIRE LENGTH MINIMIZATION IN CHANNEL ROUTING

Wire Length Minimization in Channel Routing

NP-Completeness Results, Two- and Three-Layer No-Dogleg Routing

NP-Completeness Results in Multi-Layer No-Dogleg Routing

NP- Completeness Results in Multi-Layer Restricted Dogleg Routing

ALGORITHMS FOR MINIMIZING WIRE LENGTH IN MULTI-LAYER CHANNEL ROUTING

Algorithms for Minimizing Wire Length in Vi+1Hi Channel Routing

Algorithm for Minimizing Wire Length in Two-Layer VH Channel Routing

Algorithm for Minimizing Wire Length in Three-Layer HVH Channel Routing

NOTE: Overviews/Conclusions begin and end each chapter

Subject Categories

BISAC Subject Codes/Headings:
MAT003000
MATHEMATICS / Applied
MAT022000
MATHEMATICS / Number Theory