Disjoint paths in a rectilinear grid
From MaRDI portal
Publication:1051655
DOI10.1007/BF02579432zbMath0515.05044OpenAlexW1971656597WikidataQ56987188 ScholiaQ56987188MaRDI QIDQ1051655
Publication date: 1982
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02579432
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