Routing with critical paths

DOI10.1016/0020-0190(90)90223-KzbMath0695.68045MaRDI QIDQ910228

Shai Simonson

Publication date: 1990

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

graphembeddingVLSIroutinglayout

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (1)

On the complexity of tree embedding problems

Cites Work

• On optimal linear arrangements of trees
• Some simplified NP-complete graph problems
• One-dimensional logic gate assignment and interval graphs
• Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
• Flit-serial packet routing on meshes and tori
• A polynomial algorithm for the min-cut linear arrangement of trees
• A variation on the min cut linear arrangement problem
• Complexity Results for Bandwidth Minimization
• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design

This page was built for publication: Routing with critical paths