Edge-disjoint paths in a grid bounded by two nested rectangles

DOI10.1016/0166-218X(90)90136-ZzbMath0699.68089OpenAlexW2128169435MaRDI QIDQ913521

Hitoshi Suzuki, Akira Ishiguro, Takao Nishizeki

Publication date: 1990

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(90)90136-z

zbMATH Keywords

VLSI circuitsedge-disjoint pathsmulti-layer routing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Related Items (1)

The edge-disjoint paths problem is NP-complete for series-parallel graphs

Cites Work

• Unnamed Item
• Disjoint paths in a rectilinear grid
• A linear-time algorithm for a special case of disjoint set union
• Algorithms for routing in planar graphs
• Algorithms for multicommodity flows in planar graphs
• Multicommodity flows in planar graphs
• Multicommodity flows in graphs
• An Efficient Algorithm for Finding Multicommodity Flows in Planar Networks
• Routing through a generalized switchbox
• On the routability of a convex grid

This page was built for publication: Edge-disjoint paths in a grid bounded by two nested rectangles