Skip to main content
Springer Nature Link
Log in

On-Line Maximum Matching in Complete Multipartite Graphs with Implications to the Minimum ADM Problem on a Star Topology

  • Conference paper
Structural Information and Communication Complexity (SIROCCO 2009)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5869))

  • 520 Accesses

Abstract

One of the basic problems in optical networks is assigning wavelengths to (namely, coloring of) a given set of lightpaths so as to minimize the number of ADM switches. In this paper we present a connection between maximum matching in complete multipartite graphs and ADM minimization in star networks. A tight 2/3 competitive ratio for finding a maximum matching implies a tight 10/9 competitive ratio for finding a coloring that minimizes the number of ADMs.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Azar, Y., Chaiutin, Y.: Optimal node routing. In: The proceedings of the 23rd International Symposium on Theoretical Aspects of Computer Science, Marseille, France, February 2006, pp. 596–607 (2006)

    Google Scholar 

  2. Azar, Y., Naor, J(S.), Rom, R.: The competitiveness of on-line assignments. In: The proceedings of the 13th SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA, January 2002, pp. 203–210 (2002)

    Google Scholar 

  3. Azar, Y., Richter, Y.: Management of multi-queue switches in QoS networks. Algorithmica 43(1-2), 81–96 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  4. Birnbaum, B., Mathieu, C.: On-line bipartite matching made simple. SIGACT News 39(1), 80–87 (2008)

    Article  Google Scholar 

  5. Călinescu, G., Wan, P.-J.: Traffic partition in WDM/SONET rings to minimize SONET ADMs. Journal of Combinatorial Optimization 6(4), 425–453 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  6. Epstein, L., Levin, A.: Better bounds for minimizing SONET ADMs. In: Persiano, G., Solis-Oba, R. (eds.) WAOA 2004. LNCS, vol. 3351, pp. 281–294. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  7. Epstein, L., Levin, A.: Better bounds for minimizing sonet adms. J. Comput. Syst. Sci. 75(2), 122–136 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  8. Gerstel, O., Lin, P., Sasaki, G.: Wavelength assignment in a WDM ring to minimize cost of embedded SONET rings. In: INFOCOM 1998, Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies, pp. 69–77 (1998)

    Google Scholar 

  9. Goel, G., Mehta, A.: Online budgeted matching in random input models with applications to adwords. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA, January 2008, pp. 982–991 (2008)

    Google Scholar 

  10. Gerstel, O., Ramaswami, R., Sasaki, G.: Cost effective traffic grooming in WDM rings. In: INFOCOM 1998, Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies (1998)

    Google Scholar 

  11. Kalyanasundaram, B., Pruhs, K.: On-line weighted matching. J. Algorithms 14(3), 478–488 (1993)

    Article  MATH  Google Scholar 

  12. Karp, R.M., Vazirani, U.V., Vazirani, V.V.: An optimal algorithm for on-line bipartite matching (1990)

    Google Scholar 

  13. Sitton, D.: Maximum matchings in complete multipartite graphs. Furman University Electronic Journal of Undergraduate Mathematics 2, 6–16 (1996)

    Google Scholar 

  14. Shalom, M., Wong, P.W.H., Zaks, S.: Optimal on-line colorings for minimizing the number of ADMs in optical networks. In: Pelc, A. (ed.) DISC 2007. LNCS, vol. 4731, pp. 435–449. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  15. Shalom, M., Zaks, S.: A 10/7 + ε approximation scheme for minimizing the number of ADMs in SONET rings. In: First Annual International Conference on Broadband Networks, San-José, California, USA, October 2004, pp. 254–262 (2004)

    Google Scholar 

  16. Zhou, F., Chen, G., Xu, Y., Gu, J.: Minimizing ADMs on WDM directed fiber trees. Journal of Computer Science & Technology 18(8), 725–731 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  17. Zhu, K., Mukherjee, B.: A review of traffic grooming in WDM optical networks: Architecture and challenges. Optical Networks Magazine 4(2), 55–64 (2003)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. TelHai Academic College, Upper Galilee, 12210, Israel

    Mordechai Shalom

  2. Department of Computer Science, The University of Liverpool, Liverpool, UK

    Prudence W. H. Wong

  3. Department of Computer Science, Technion, Haifa, Israel

    Shmuel Zaks

Authors
  1. Mordechai Shalom
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Prudence W. H. Wong
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Shmuel Zaks
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Technion – Israel Institute of Technology, Dept. of Industrial Engineering and Management,, Technion City, 32000, Haifa, Israel

    Shay Kutten

  2. Faculty of Mechanical Engineering, University of Maribor, FS, Smetanova 17, 2000, Maribor, Slovenia

    Janez Žerovnik

Rights and permissions

Reprints and permissions

Copyright information

© 2010 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Shalom, M., Wong, P.W.H., Zaks, S. (2010). On-Line Maximum Matching in Complete Multipartite Graphs with Implications to the Minimum ADM Problem on a Star Topology. In: Kutten, S., Žerovnik, J. (eds) Structural Information and Communication Complexity. SIROCCO 2009. Lecture Notes in Computer Science, vol 5869. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11476-2_22

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-11476-2_22

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-11475-5

  • Online ISBN: 978-3-642-11476-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation