access icon free DIAMOND: a distributed algorithm for vertex coloring problems and resource allocation

© The Institution of Engineering and Technology
Received 02/11/2018, Accepted 15/08/2019, Revised 15/04/2019, Published 15/08/2019

The vertex colouring problem (VCP) and its generalisations have myriad applications in computer networks. To solve the VCP with colours, numerous distributed algorithms based on LOCAL model have been proposed to reduce time complexity (the number of rounds), where is the maximum vertex degree in the graph. In this paper, the authors present a distributed algorithm based on modified LOCAL model (DIAMOND) that reduces the number of rounds to one. It greedily solves the VCP with at most colours. Computational results on Geometry (GEOM) graphs show that the number of used colours to colour each instance using DIAMOND is about . DIAMOND is easily extended to solve greedily generalised VCPs in only one round. Moreover, they present two efficient resource allocation algorithms using DIAMOND. They allocate more resource to the graph compared with -colouring and even to -colouring algorithms, where is the average vertex degree of the graph. They run in two and rounds.

Inspec keywords: graph colouring; distributed algorithms; resource allocation

Other keywords: resource allocation algorithms; vertex colouring problem; distributed algorithms; modified LOCAL model; distributed algorithm; GEOM graphs; DIAMOND; myriad applications; greedily generalised VCP; computer networks; maximum vertex degree

Subjects: Combinatorial mathematics; Combinatorial mathematics; Parallel programming and algorithm theory; Combinatorial mathematics; Algebra, set theory, and graph theory

References

    1. 1)
      • 24. Stanczak, S., Wiczanowski, M., Boche, H.: ‘Distributed utility-based power control: objectives and algorithms’, IEEE Trans. Signal Process., 2007, 55, (10), pp. 5058–5068.
    2. 2)
      • 11. Kothapalli, K., Scheideler, C., Onus, M., et al: ‘Distributed coloring in O~(log⁡n) bit rounds’. Proc. 20th IEEE Int. Parallel and Distributed Processing Symp., Rhodes Island, 2006, vol. 24, (3), p. 10.
    3. 3)
      • 15. Barenboim, L., Elkin, M., Pettie, S., et al: ‘The locality of distributed symmetry breaking’, J. ACM, 2016, 63, (3), pp. 20:1–20:45.
    4. 4)
      • 5. Dias, B., de Freitasa, R., Maculan, N., et al: ‘Solving the bandwidth coloring problem applying constraint and integer programming techniques’, 2016.
    5. 5)
      • 14. Harris, D.G., Schneider, J., Su, H.-H.: ‘Distributed (Δ+1at)-coloring in sublogarithmic rounds’. Proc. 48th Annual ACM Symp. Theory of Computing, series STOC ‘16, Cambridge, MA, USA, 2016, pp. 465–478.
    6. 6)
      • 1. Elkin, M., Pettie, S., Su, H.-H.: ‘(2▵−1)-edge-coloring is much easier than maximal matching in the distributed setting’. Proc. 26th Annual ACM-SIAM Symp. Discrete Algorithms, series SODA ‘15. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2015, pp. 355–370.
    7. 7)
      • 10. Robson, J.M., Metivier, Y., Saheb-Djahromi, N., et al: ‘About randomised distributed graph colouring and graph partition algorithms’, Inf. Comput., 2010, 208, (11), pp. 1296–1304.
    8. 8)
      • 18. Linial, N.: ‘Locality in distributed graph algorithms’, SIAM J. Comput., 1992, 21, (1), pp. 193–201.
    9. 9)
      • 20. Barenboim, L., Elkin, M., Pettie, S., et al: ‘The locality of distributed symmetry breaking’. 2012 IEEE 53rd Annual Symp. Foundations of Computer Science, Zurich, Switzerland, October 2012, pp. 321–330.
    10. 10)
      • 4. Wang, K., Zhao, M., Zhou, W.: ‘Traffic-aware graph-based dynamic frequency reuse for heterogeneous cloud-ran’. 2014 IEEE Global Communications Conf., Austin, TX, USA, December 2014, pp. 2308–2313.
    11. 11)
      • 28. Dai, L., Chen, W., Cimini, L.J., et al: ‘Fairness improves throughput in energy-constrained cooperative ad-hoc networks’, IEEE Trans. Wirel. Commun., 2009, 8, (7), pp. 3679–3691.
    12. 12)
      • 27. Jain, R., Chiu, D., Hawe, W.: ‘A quantitative measure of fairness and discrimination for resource allocation in shared computer systems’, CoRR, 1998, cs.NI/9809099.
    13. 13)
      • 3. Cheng, S.H., Huang, C.Y.: ‘Coloring-based inter-WBAN scheduling for mobile wireless body area networks’, IEEE Trans. Parallel Distrib. Syst., 2013, 24, (2), pp. 250–259.
    14. 14)
      • 25. Zheng, D., Zhang, J.: ‘A two-phase utility maximization framework for wireless medium access control’, IEEE Trans. Wirel. Commun., 2007, 6, (12), pp. 4207–4299.
    15. 15)
      • 26. Shi, H., Prasad, R.V., Onur, E., et al: ‘Fairness in wireless networks: issues, measures and challenges’, IEEE Commun. Surv. Tutor., 2014, 16, (1), pp. 5–24, First 2014.
    16. 16)
      • 30. Jin, Y., Hao, J.K.: ‘Effective learning-based hybrid search for bandwidth coloring’, IEEE Trans. Syst. Man Cybern. Syst., 2015, 45, (4), pp. 624–635.
    17. 17)
      • 12. Xiangjing, L., Zhipeng, L.: ‘Multistart iterated tabu search for bandwidth coloring problem’, Comput. Oper. Res., 2013, 40, (5), pp. 1401–1409.
    18. 18)
      • 21. Hella, L., Järvisalo, M., Kuusisto, A., et al: ‘Weak models of distributed computing, with connections to modal logic’, Distrib. Comput., 2015, 28, (1), pp. 31–53.
    19. 19)
      • 16. Schneider, J., Wattenhofer, R.: ‘A new technique for distributed symmetry breaking’. Proc. 29th ACM SIGACT-SIGOPS Symp. Principles of Distributed Computing, series PODC ‘10, Zurich, Switzerland, 2010, pp. 257–266.
    20. 20)
      • 8. Behzad, A., Rubin, Z.: ‘Multiple access protocol for power-controlled wireless access nets’, IEEE Trans. Mob. Comput., 2004, 3, (4), pp. 307–316.
    21. 21)
      • 7. Colombet, Q., Boissinot, B., Brisk, P., et al: ‘Graph-coloring and treescan register allocation using repairing’. 2011 Proc. 14th Int. Conf. Compilers, Architectures and Synthesis for Embedded Systems (CASES), Taipei, Taiwan, October 2011, pp. 45–54.
    22. 22)
      • 2. Malaguti, E., Toth, P.: ‘A survey on vertex coloring problems’, Int. Trans. Oper. Res., 2009, 17, (1), pp. 1–34.
    23. 23)
      • 9. Metivier, Y., Robson, J.M., Saheb-Djahromi, N., et al: ‘An analysis of an optimal bit complexity randomised distributed vertex colouring algorithm’. Int. Conf. Principles of Distributed Systems, Nîmes, France, December 2009, pp. 359–364.
    24. 24)
      • 17. Johansson, O.: ‘Simple distributed (Δ+1)-coloring of graphs’, Inf. Process. Lett., 1999, 70, pp. 229–232.
    25. 25)
      • 29. Yousefi'zadeh, H., Jafarkhani, H., Habibi, A.: ‘Layered media multicast control (LMMC): rate allocation and partitioning’, IEEE/ACM Trans. Netw., 2005, 13, (3), pp. 540–553.
    26. 26)
      • 13. Lim, A., Zhu, Y., Lou, Q., et al: ‘Heuristic methods for graph coloring problems’. Proc. 2005 ACM Symp. Applied Computing, series SAC ‘05, Santa Fe, New Mexico, 2005, pp. 933–939.
    27. 27)
      • 19. Han, K., Kim, C.: ‘An evolutionary approach for graph multi-coloring problem’, Appl. Math. Sci., 2015, 9, (34), pp. 1677–1684.
    28. 28)
      • 23. Tanenbaum, A.S.: ‘Computer networks’ (Prentice-Hall, Amsterdam, The Netherlands, 2011, 5th edn.).
    29. 29)
      • 6. Cai, X., Zheng, J., Zhang, Y.: ‘A graph-coloring based resource allocation algorithm for d2d communication in cellular networks’. 2015 IEEE Int. Conf. Communications (ICC), London, UK, June 2015, pp. 5429–5434.
    30. 30)
      • 22. Hefetz, D., Kuhn, F., Maus, Y., et al: ‘Polynomial lower bound for distributed graph coloring in a weak local model’, in Gavoille, C., Ilcinkas, D. (Eds.): ‘Distributed computing’ (Springer Berlin Heidelberg, Berlin, Heidelberg, 2016), pp. 99–113.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-net.2018.5204
Loading

Related content

content/journals/10.1049/iet-net.2018.5204
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading