Routing with critical paths

DOI10.1016/0020-0190(90)90223-KzbMATH Open0695.68045MaRDI QIDQ910228FDOQ910228

Authors: Shai Simonson 

Publication date: 1990

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

Recommendations

• scientific article; zbMATH DE number 4211829
• Algorithms for routing in planar graphs
• scientific article; zbMATH DE number 4039320
• Algorithms for finding paths with multiple constraints
• scientific article; zbMATH DE number 4051669

zbMATH Keywords

graphembeddingroutingVLSIlayout

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)

Cites Work

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

Cited In (2)

• Routing traffic at hub facilities
• On the complexity of tree embedding problems

This page was built for publication: Routing with critical paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q910228)