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

DOI10.1016/0166-218X(90)90136-ZMaRDI QIDQ913521zbMATH OpenOpenAlexFDO

Authors 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

edge-disjoint pathsVLSI circuitsmulti-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)

Recommendations

• Efficient Algorithms for Finding the Maximum Number of Disjoint Paths in Grids
• On local routing of two-terminal nets
• A linear-time algorithm for edge-disjoint paths in planar graphs
• scientific article; zbMATH DE number 1445371
• Edge-disjoint paths in planar graphs

Cites work

• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• A linear-time algorithm for a special case of disjoint set union
• Algorithms for multicommodity flows in planar graphs
• Algorithms for routing in planar graphs
• An Efficient Algorithm for Finding Multicommodity Flows in Planar Networks
• Disjoint paths in a rectilinear grid
• Multicommodity flows in graphs
• Multicommodity flows in planar graphs
• On the routability of a convex grid
• Routing through a generalized switchbox

Cited in

(5)

• Escaping a grid by edge-disjoint paths
• Efficient Algorithms for Finding the Maximum Number of Disjoint Paths in Grids
• scientific article; zbMATH DE number 1445371 (Why is no real title available?)
• The edge-disjoint paths problem is NP-complete for series-parallel graphs
• Finding edge-disjoint paths in partial k-trees

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

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