Approximation Strategies for Routing Edge Disjoint Paths in Complete Graphs

  • Adrian Kosowski
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4056)


The paper deals with the well known Maximum Edge Disjoint Paths Problem (MaxEDP), restricted to complete graphs. We propose an off-line 3.75-approximation algorithm and an on-line 6.47-approximation algorithm, improving earlier 9-approximation algorithms due to Carmi, Erlebach and Okamoto (Proceedings WG’03, 143–155). Next, it is shown that no on-line algorithm for the considered problem is ever better than a 1.50-approximation. Finally, the proposed approximation techniques are adapted for other routing problems in complete graphs, leading to an off-line 3-approximation (on-line 4-approximation) for routing with minimum edge load, and an off-line 4.5-approximation (on-line 6-approximation) for routing with a minimum number of WDM wavelengths.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Andrews, M., Zhang, L.: Hardness of the undirected edge-disjoint paths problem. In: Proc. STOC 2005, pp. 276–283 (2005)Google Scholar
  2. 2.
    Beauquier, B., Bermond, J.C., Gargano, L., Hell, P., Pèrennes, S., Vaccaro, U.: Graph problems arising from wavelength routing in all-optical networks. In: Proc. WOCS 1997, Geneve, Switzerland (1997)Google Scholar
  3. 3.
    Białogrodzki, J.: Path Coloring and Routing in Graphs. In: Kubale, M. (ed.) Graph Colorings. Contemporary Math, vol. 352, pp. 139–152. AMS, USA (2004)Google Scholar
  4. 4.
    Carmi, P., Erlebach, T., Okamoto, Y.: Greedy edge-disjoint paths in complete graphs. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol. 2880, pp. 143–155. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  5. 5.
    Choplin, S., Narayanan, L., Opatrny, J.: Two-Hop Virtual Path Layout in Tori. In: Kralovic, R., Sýkora, O. (eds.) SIROCCO 2004. LNCS, vol. 3104, pp. 69–78. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  6. 6.
    Erlebach, T., Jansen, K.: The complexity of path coloring and call scheduling. Theoret. Comp. Sci. 255, 33–50 (2001)zbMATHCrossRefMathSciNetGoogle Scholar
  7. 7.
    Erlebach, T., Jansen, K.: The Maximum Edge-Disjoint Paths Problem in Bidirected Trees. SIAM J. Discret. Math. 14, 326–355 (2001)zbMATHCrossRefMathSciNetGoogle Scholar
  8. 8.
    Erlebach, T., Vukadinović, D.: New results for path problems in generalized stars, complete graphs, and brick wall graphs. In: Freivalds, R. (ed.) FCT 2001. LNCS, vol. 2138, pp. 483–494. Springer, Heidelberg (2001)CrossRefGoogle Scholar
  9. 9.
    Favrholdt, L.M., Nielsen, M.N.: On-line edge-coloring with a fixed number of colors. Algorithmica 35, 176–191 (2003)zbMATHCrossRefMathSciNetGoogle Scholar
  10. 10.
    Fiorini, S., Wilson, R.J.: Edge-Colourings of Graphs. Pittman, USA (1977)zbMATHGoogle Scholar
  11. 11.
    Gabow, H.N.: Data structures for weighted matching and nearest common ancestors with linking. In: Proc. SODA 1990, pp. 434–443 (1990)Google Scholar
  12. 12.
    Guruswami, V., et al.: Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. J. Comput. Syst. Sci. 67, 473–496 (2003)zbMATHCrossRefMathSciNetGoogle Scholar
  13. 13.
    Kolman, P., Scheideler, C.: Improved bounds for the unsplittable flow problem. In: Proc. SODA 2002, pp. 184–193 (2002)Google Scholar
  14. 14.
    Ma, B., Wang, L.: On the inapproximability of disjoint paths and minimum Steiner forest with bandwidth constraints. J. Comput. Syst. Sci. 60, 1–12 (2000)zbMATHCrossRefMathSciNetGoogle Scholar
  15. 15.
    Srinivasan, A.: Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problems. In: Proc. FOCS 1997, pp. 416–425 (1997)Google Scholar
  16. 16.
    Tutte, W.T.: A short proof of the factor theorem for finite graphs. Canad. J. Math. 6, 347–352 (1954)zbMATHMathSciNetCrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Adrian Kosowski
    • 1
  1. 1.Department of Algorithms and System ModelingGdańsk University of Technology 

Personalised recommendations