Jon Kleinberg
Éva Tardos
- 1.A. Agganval, A. Bar-Noy, D. Coppersmith, R. Ra-maswami, B. Schieber, M. Sudan, "Ef%cient routing and scheduling algorithms for optical networks," Proc. 5th ACM-SIAM SODA, 1994, pp. 412-423. Google Scholar
Digital Library
- 2.Y. Aumann, Y. Rabani, "Improved bounds for all-optical routing," Proc. 6th ACM-SIAM SODA, 1995, pp. 567-576. Google ScholarDigital Library
- 3.B. Awerbuch, Y. Azar, S. Plotkin, "Throughput-Competitive Online Routing," Proc. 34th IEEE FOCS, 1993, pp. 32-40.Google Scholar
- 4.B. Awerbuch, R. Gawlick, F.T. Leighton, Y. Rabani, "On-line admission control and circuit routing for high perfor-mance computing and communication," Proc. 35th IEEE FOCS, 1994, pp. 412423.Google Scholar
- 5.A, Broder, A. Frieze. S. Suen. E. Upfd. "Optimal con-struction of edge-disjoint paths in random graphs," Proc. 5th ACM-SIAM SODA, 1994, pp. 603-612. Google ScholarDigital Library
- 6.A. Broder, A. Frieze, E. Upfal, "Existence and constmc-tion of edge-disjoint paths on expander graphs," Proc. 24th ACM STOC, 1992, pp. 140-149. Google ScholarDigital Library
- 7.J. Davies, C. McDiarmid, "Disjoint Common Tmversals in &xnge Structures: 1 Landon Math. SOC.,14(1976), pp.Google Scholar
- 8.J. E&onds, "Minimum partition of a matroid into inde-pendent subsets.'',J. Res. Nat. Bur. Standards B, 69(1965), pp. 67-72.Google Scholar
- 9.J. E&nods, "Matroid intersection," A,nnals of Discrete Mathematics, 4(1979), pp. 39-49.Google ScholarCross Ref
- 10.A, Frank, "Edge-disjoint paths in planar graphs," J. Comb. Theory Ser. B, 39(1985), pp. 164-178.Google ScholarCross Ref
- 11.A. Frank, "Packing paths. cuts, and circuits : a survey." in Paths, Flows, and VL.SI-Layout, B. Korte, L. Lowisz, ~g~oPriimel, A. Schrijver, Eds., Berlbx Springer-Verlag,Google Scholar
- 12.N. Garg, V. Vazirani, M. Ymmakakis, "Primal-dual ap-proximation algorithms for integral flow and multicut in trees, with applications to matching and set cover," Proc. ICALP, 1993, pp. 64-75. Google ScholarDigital Library
- 13.R.M. Kaqx "Reducibfity among combinatorial prob-lems," Complexity of Computer Computations. R.E. Miller, J.W. Thatcher, E&., New York Plenum Press, 1972.Google Scholar
- 14.M.E. Kramer, J. van Leeuwen, "The complexity of wire routing and finding the minimum area layouts for arbitrary VLSI circuits; Advances in Computing Research 2: VLSI Theory, F.P. Preparata, Ed., London JA3 Press, 1984.Google Scholar
- 15.M. Middendorf, F. Pfeiffer, "On the complexity of the disjoint paths problemy Combinatorics, 13(1993).Google Scholar
- 16.H. Okamura, P. Seymour. "Multicommodity flows in pla-nar graphs," J. Comb. Theory Ser. B, 31(1981), pp. 75-81.Google ScholarCross Ref
- 17.D. Peleg, E. Upfal, "Disjoint paths on expander gmphs~' Combinatorics, 9(1989), pp. 289-313.Google Scholar
- 18.P. Raghavan, "Probabilistic construction of deterministic algorithms: approximating packing integer programs," J. Computer and System Sciences, 37(1988), pp. 130-143. Google ScholarDigital Library
- 19.P. Raghavan. C.D. Thompson, "Randomized rounding a technique for provably good algorithms and algorithmic proofs," Combinatorics, 7(1987), pp. 365-374. Google ScholarDigital Library
- 20.P. Raghavan, E. Upfal, "Efficient all-optical routingy Proc. 26th ACM STOC. 1994, pp. 134-143. Google ScholarDigital Library
- 21.D. Wagner, K. Weihe, "A linear time algorithm for mul-ticommodity flow in phmar graphs," Proc. First European Symposium on Algorithms, 1993, pp. 3(84-395. Google ScholarDigital Library
- 22.~fj:A. Welsh, Matroid Theory, London Academic Press, 1976Google Scholar
Index Terms
- Approximations for the disjoint paths problem in high-diameter planar networks
Recommendations
Approximations for the Disjoint Paths Problem in High-Diameter Planar Networks
We consider the problem of connecting distinguished terminal pairs in a graph via edge-disjoint paths. This is a classical NP-complete problem for which no general approximation techniques are known; it has recently been brought into focus in papers ...
On shortest disjoint paths in planar graphs
For a graph G and a collection of vertex pairs {(s"1,t"1),...,(s"k,t"k)}, the k disjoint paths problem is to find k vertex-disjoint paths P"1,...,P"k, where P"i is a path from s"i to t"i for each i=1,...,k. In the corresponding optimization problem, the ...
A linear time algorithm for the induced disjoint paths problem in planar graphs
In this paper, we consider a problem which we call the induced disjoint paths problem (IDPP) for planar graphs. We are given a planar graph G and a collection of vertex pairs {(s"1,t"1),...,(s"k,t"k)}. The objective is to find k paths P"1,...,P"k such ...
Comments