Disjoint paths in a rectilinear grid

DOI10.1007/BF02579432zbMath0515.05044OpenAlexW1971656597WikidataQ56987188 ScholiaQ56987188MaRDI QIDQ1051655

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

multicommodity flowsedge-disjoint pathsgood algorithminfinite plane grid

Mathematics Subject Classification ID

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

Related Items

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

Cites Work

• Unnamed Item
• Multicommodity flows in planar graphs
• Über die Maximalzahl kantendisjunkter A-Wege
• Maximum-Minimum Sätze über Graphen
• On Odd Cuts and Plane Multicommodity Flows
• The Factors of Graphs