Node-Disjoint Paths on the Mesh and a New Trade-Off in VLSI Layout

DOI10.1137/S0097539796312733zbMath0947.68113OpenAlexW2057427520MaRDI QIDQ4943873

David P. Williamson, Alok Aggarwal, Jon M. Kleinberg

Publication date: 19 March 2000

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539796312733

zbMATH Keywords

combinatorial optimizationVLSI layoutdisjoint paths problem

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

Multicriteria movement synchronization scheduling problems and algorithms ⋮ Routing vertex disjoint Steiner-trees in a cubic grid and connections to VLSI ⋮ Unnamed Item ⋮ A note on solving the fleet quickest routing problem on a grid graph ⋮ Complexity of pairwise shortest path routing in the grid ⋮ Improved Algorithms for the 2-Vertex Disjoint Paths Problem ⋮ On the isometric path partition problem ⋮ New solutions for disjoint paths in P systems

This page was built for publication: Node-Disjoint Paths on the Mesh and a New Trade-Off in VLSI Layout