Maximum integer multiflow and minimum multicut problems in two-sided uniform grid graphs

Adamy, 2002, Call control in rings, vol. 2380, 788 Cǎlinescu, 2003, Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width, Journal of Algorithms, 48, 333, 10.1016/S0196-6774(03)00073-7 Chan, 2000, Efficient algorithms for finding the maximum number of disjoint paths in grids, Journal of Algorithms, 34, 337, 10.1006/jagm.1999.1054 Costa, 2005, Minimal multicut and maximal integer multiflow: A survey, EJOR, 162, 55, 10.1016/j.ejor.2003.10.037 Dahlhaus, 1994, The complexity of multiterminal cuts, SIAM Journal on Computing, 23, 864, 10.1137/S0097539792225297 Formann, 1993, Routing through a dense channel with minimum total wire length, Journal of Algorithms, 15, 267, 10.1006/jagm.1993.1041 Frank, 1982, Disjoint paths in a rectilinear grid, Combinatorica, 2, 361, 10.1007/BF02579432 Frank, 1985, Edge-disjoint paths in planar graphs, Journal of Combinatorial Theory, Series B, 39, 164, 10.1016/0095-8956(85)90046-2 Frank, 1990, Packing paths, circuits and cuts—a survey, vol. 9, 47 Garey, 1979 Garg, 1997, Primal-dual approximation algorithms for integral flow and multicut in trees, Algorithmica, 18, 3, 10.1007/BF02523685 J. Kleinberg, É. Tardos, Disjoint paths in densely embedded graphs, in: Proceedings 36th IEEE FOCS, 1995, pp. 52–61 J. Kleinberg, Approximation algorithms for disjoint paths problems, PhD thesis, MIT, Cambridge, MA, 1996 Kramer, 1984, The complexity of wire routing and finding the minimum area layouts for arbitrary VLSI circuits, 129 Marx, 2004, Eulerian disjoint paths problem in grid graphs is NP-complete, Discrete Applied Mathematics, 143, 336, 10.1016/j.dam.2003.12.003 Okamura, 1981, Multicommodity flows in planar graphs, Journal of Combinatorial Theory, Series B, 31, 75, 10.1016/S0095-8956(81)80012-3 Schrijver, 1986, Theory of Linear and Integer Programming K. Weihe, Edge-disjoint routing in plane switch graphs in linear time, in: Proceedings 40th IEEE FOCS, New York City, 1999, pp. 330–340