IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 1993 · 28 citations · 7 references
EngineeringComputer EngineeringElectrical EngineeringAlgorithmsField-programmable Gate ArraysOptimizationField-programmable Gate Array ArchitectureFpga ArchitectureProgrammable Logic DevicesRoutingRouting AlgorithmsSwitching TechniquesChannel RoutingCircuit RoutingPolynomial Time ComplexityPolynomial-time AlgorithmsRouting In Field-programmable Gate ArraysSegment Routing
Novel problems concerning routing in a segmented routing channel are introduced. These problems are fundamental to routing and design automation for field programmable gate arrays (FPGAs), a new type of electrically programmable VLSI. The first known theoretical results on the combinatorial complexity and algorithm design for segmented channel routing are presented. It is shown that the segmented channel routing problem is in general NP-complete. Efficient polynomial time algorithms for a number of important special cases are presented.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
7