| References: [1] Aggarwal, Alok., Kleinberg, Jon., Williamson, David P. (2000). Node-disjoint paths on the mesh and a new trade-off in VLSI layout. SIAM Journal on Computing, 29(4), 1321–1333.
[2] Ajtai, Miklós., Chvátal, Václav., Newborn, Monroe M., Szemerédi, Endre. (1982). Crossing-free subgraphs. In Gert Sabidussi, Peter L. Hammer, Alexander Rosa, and Jean Turgeon (Eds.), Theory and Practice of Combinatorics: A collection of articles honoring Anton Kotzig on the occasion of his sixtieth birthday (Vol. 60 of North-Holland Mathematics Studies, pp. 9–12). North-Holland.
[3] Andrews, Matthew. (2010). Approximation algorithms for the edge-disjoint paths problem via Raecke decompositions. In Proceedings of IEEE FOCS, (pp. 277–286).
[4] Andrews, Matthew., Chuzhoy, Julia., Guruswami, Venkatesan., Khanna, Sanjeev., Talwar, Kunal., Zhang, Lisa. (2010). Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs. Combinatorica, 30(5), 485–520.
[5] Andrews, Matthew., Zhang, Lisa. (2005). Hardness of the undirected edge-disjoint paths problem. In STOC, (pp. 276–283).
[6] Arora, Sanjeev., Lund, Carsten., Motwani, Rajeev., Sudan, Madhu., Szegedy, Mario. (1998). Proof verification and the hardness of approximation problems. Journal of the ACM, 45, 501–555.
[7] Arora, Sanjeev., Safra, Shmuel. (1998). Probabilistic checking of proofs: A new characterization of np. Journal of the ACM, 45, 70–122.
[8] Aumann, Yonatan., Rabani, Yuval. (1995). Improved bounds for all optical routing. In Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, SODA’95, (pp.
567–576). Society for Industrial and Applied Mathematics.
[9] Chekuri, Chandra., Chuzhoy, Julia. (2013). Half-integral all-or-nothing flow. Unpublished Manuscript.
[10] Chekuri, Chandra, Ene, Alina. (2013). Poly-logarithmic approximation for maximum node disjoint paths with constant congestion. In Proc. of ACM-SIAM SODA, 2013.
[11] Chekuri, Chandra., Khanna, Sanjeev., Shepherd, F. Bruce. (2004). Edge-disjoint paths in planar graphs. In Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on, (pp. 71–80). IEEE.
[12] Chekuri, Chandra., Khanna, Sanjeev., Shepherd, F. Bruce. (2005). Multicommodity flow, welllinked terminals, and routing problems. In Proc. of ACM STOC, (pp. 183–192).
[13] Chekuri, Chandra., Khanna, Sanjeev., Shepherd, F. Bruce. (2006). An O(pn) approximation and integrality gap for disjoint paths and unsplittable flow. Theory of Computing, 2(1), 137–146.
[14] Chuzhoy, Julia. (2012). Routing in undirected graphs with constant congestion. In Proc. of ACM STOC, (pp. 855–874).
[15] Chuzhoy, Julia., Li, Shi. (2012). A polylogarithmic approximation algorithm for edge- disjoint paths with congestion 2. In: Proc. of IEEE FOCS, 2012.
[16] Cutler, M., Shiloach, Y. (1978). Permutation layout. Networks, 8, 253–278.
[17] Karp, R. (1975). On the complexity of combinatorial problems. Networks, 5, 45–68.
[18] Kawarabayashi, Ken-Ichi, Kobayashi, Yusuke. (2013). An o(log n)-approximation algo
rithm for the edge-disjoint paths problem in eulerian planar graphs. ACM Transactions on Algorithms, 9(2), 16:1–16:13.
[19] Kleinberg, Jon M. (2005). An approximation algorithm for the disjoint paths problem in even degree planar graphs. In FOCS’05, (pp. 627–636).
[20] Jon M. Kleinberg and Éva Tardos. Disjoint paths in densely embedded graphs. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science, pages 52–61, 1995.
[21] Jon M. Kleinberg and Éva Tardos. Approximations for the disjoint paths problem in high diameter planar networks. Journal of Computer and System Sciences, 57(1):61–73, 1998.
[22] Stavros G. Kolliopoulos and Clifford Stein. Approximating disjoint-path problems using packing integer programs. Mathematical Programming, 99:63–87, 2004.
[23] Frank Thomson Leighton. Complexity Issues in VLSI: Optimal Layouts for the Shuffle-exchange Graph and Other Networks. MIT Press, Cambridge, MA, USA, 1983.
[24] Harald Räcke. Minimizing congestion in general networks. In: Proc. of IEEE FOCS, pages 43–52, 2002.
[25] Prabhakar Raghavan and Clark D. Tompson. Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica, 7:365–374, December 1987.
[26] Satish Rao and Shuheng Zhou. Edge disjoint paths in moderately connected graphs. SIAM Journal on Computing, 39(5):1856–1887, 2010.
[27] N. Robertson and P. D. Seymour. Outline of a disjoint paths algorithm. In Paths, Flows and VLSI-Layout. Springer-Verlag, 1990.
[28] Neil Robertson and Paul D. Seymour. Graph minors. VII. disjoint paths on a surface. Journal of Combinatorial Theory, Series B, 45(2):212–254, 1988.
[29] Neil Robertson and Paul D Seymour. Graph minors. XIII. the disjoint paths problem. Journal of Combinatorial Theory, Series B, 63(1):65–110, 1995.
[30] Loïc Seguin-Charbonneau and F. Bruce Shepherd. Maximum edge-disjoint paths in planar graphs with congestion 2. In Proceedings of the 2011 IEEE 52Nd Annual Symposium on Foundations of Computer Science, FOCS’11, pages 200–209, Washington, DC, USA, 2011. IEEE Computer Society. |
Author Rights 
