[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Local Algorithms for Edge Colorings in UDGs

  • Conference paper
Graph-Theoretic Concepts in Computer Science (WG 2009)

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

Included in the following conference series:

  • 1074 Accesses

Abstract

In this paper we consider two problems: the edge coloring and the strong edge coloring problems on unit disk graphs (UDGs). Both problems have important applications in wireless sensor networks as they can be used to model link scheduling problems in such networks. It is well known that both problems are NP-complete, and approximation algorithms for them have been extensively studied under the centralized model of computation. Centralized algorithms, however, are not suitable for ad-hoc wireless sensor networks whose devices typically have limited resources, and lack the centralized coordination.

We develop local distributed approximation algorithms for the edge coloring and the strong edge coloring problems on unit disk graphs. For the edge coloring problem, our local distributed algorithm has approximation ratio 2 and locality 50. We show that the locality upper bound can be improved to 28 while keeping the same approximation ratio, at the expense of increasing the computation time at each node. For the strong edge coloring problem on UDGs, we present two local distributed algorithms with different tradeoffs between their approximation ratio and locality. The first algorithm has ratio 128 and locality 22, whereas the second algorithm has ratio 10 and locality 180.

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. Barrett, C., Kumar, V., Marathe, M., Thite, S., Istrate, G.: Strong edge coloring for channel assignment in wireless radio networks. In: PERCOMW 2006, pp. 106–110 (2006)

    Google Scholar 

  2. Czyzowicz, J., Dobrev, S., Kranakis, E., Opatrny, J., Urrutia, J.: Local edge colouring of yao-like subgraphs of unit disk graphs. In: Prencipe, G., Zaks, S. (eds.) SIROCCO 2007. LNCS, vol. 4474, pp. 195–207. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  3. Gandham, S., Dawande, M., Prakash, R.: Link scheduling in sensor networks: distributed edge coloring revisited. In: INFOCOM, pp. 2492–2501 (2005)

    Google Scholar 

  4. Holyer, I.: The NP-completeness of edge-coloring. SIAM J. Comput. 10(4), 718–720 (1981)

    Article  MATH  MathSciNet  Google Scholar 

  5. Ito, T., Kato, A., Zhou, X., Nishizeki, T.: Algorithms for finding distance-edge-colorings of graphs. J. Discrete Algorithms 5(2), 304–322 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  6. Kanj, I., Wiese, A., Zhang, F.: Computing the k-hop neighborhoods locally. Technical report # 08-007 at: http://www.cdm.depaul.edu/research/Pages/TechnicalReports.aspx

  7. Kodialam, M., Nandagopal, T.: Characterizing achievable rates in multi-hop wireless mesh networks with orthogonal channels. IEEE/ACM Trans. Netw. 13(4), 868–880 (2005)

    Article  Google Scholar 

  8. Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193–201 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  9. Mahdian, M.: On the computational complexity of strong edge coloring. Discrete Applied Mathematics 118(3), 239–248 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  10. Misra, J., Gries, D.: A constructive proof of vizing’s theorem. IPL 41 (1992)

    Google Scholar 

  11. Ramanathan, S.: A unified framework and algorithm for channel assignment in wireless networks. Wirel. Netw. 5(2), 81–94 (1999)

    Article  Google Scholar 

  12. Ramanathan, S., Lloyd, E.L.: Scheduling algorithms for multihop radio networks. IEEE/ACM Trans. Netw. 1(2), 166–177 (1993)

    Article  Google Scholar 

  13. Vizing, V.: On the estimate of the chromatic class of p-graphs. Diskret. Analiz 3, 25–30 (1964)

    MathSciNet  Google Scholar 

  14. Wiese, A., Kranakis, E.: Local construction and coloring of spanners of location aware unit disk graphs. Technical report # 07-18 at, http://www.scs.carleton.ca/~kranakis/Papers/TR-07-18.pdf

Download references

Author information

Authors and Affiliations

  1. School of Computing, DePaul University, 243 S. Wabash Avenue, Chicago, IL, 60604, USA

    Iyad A. Kanj

  2. Institute für Mathematik, Technische Universität Berlin, Germany

    Andreas Wiese

  3. Department of Computer Science, Texas A&M University, College Station, TX, 77843-3112, USA

    Fenghui Zhang

Authors
  1. Iyad A. Kanj
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Andreas Wiese
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Fenghui Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. CNRS - LIRMM, 161 rue Ada, 34392, Montpellier Cedex 5, France

    Christophe Paul

  2. LIAFA, case 7014, Université Paris Diderot, 75205, Paris Cedex 13, France

    Michel Habib

Rights and permissions

Reprints and permissions

Copyright information

© 2010 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Kanj, I.A., Wiese, A., Zhang, F. (2010). Local Algorithms for Edge Colorings in UDGs. In: Paul, C., Habib, M. (eds) Graph-Theoretic Concepts in Computer Science. WG 2009. Lecture Notes in Computer Science, vol 5911. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11409-0_18

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-11409-0_18

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-11408-3

  • Online ISBN: 978-3-642-11409-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics