Disjoint paths in a rectilinear grid

DOI10.1007/BF02579432MaRDI QIDQ1051655zbMATH OpenOpenAlexDBLPWikidataFDO

Authors András Frank

Publication date 1982

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02579432

zbMATH Keywords

edge-disjoint pathsmulticommodity flowsgood algorithminfinite plane grid

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Connectivity (05C40) Applications of graph theory to circuits and networks (94C15)

Cites work

• scientific article; zbMATH DE number 3154393 (Why is no real title available?)
• Maximum-Minimum Sätze über Graphen
• Multicommodity flows in planar graphs
• On Odd Cuts and Plane Multicommodity Flows
• The Factors of Graphs
• Über die Maximalzahl kantendisjunkter A-Wege

Cited in

(16)

• Channel routing in knock-knee mode: Simplified algorithms and proofs
• Algorithms for routing in planar graphs
• Bounds for the symmetric 2-peripatetic salesman problem
• The shortest multipaths problem in a capacitated dense channel
• Maximum integer multiflow and minimum multicut problems in two-sided uniform grid graphs
• Routings for involutions of a hypercube
• Some polynomially solvable subcases of the detailed routing problem in VLSI design
• Finding edge-disjoint paths in partial k-trees
• Edge-disjoint paths in a grid bounded by two nested rectangles
• An efficient parallel logarithmic time algorithm for the channel routing problem
• Exact and approximate resolution of integral multiflow and multicut problems: Algorithms and complexity
• Parity conditions in homotopic knock-knee routing
• Edge-disjoint paths in planar graphs
• On local routing of two-terminal nets
• Optimizing area for three-layer knock-knee channel routing
• Eulerian disjoint paths problem in grid graphs is NP-complete

This page was built for publication: Disjoint paths in a rectilinear grid

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