http://iet.metastore.ingenta.com
1887

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

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

For access to this article, please select a purchase option:

Buy article PDF
$19.95
(plus tax if applicable)
Add to cart
Buy Knowledge Pack
10 articles for $120.00
(plus taxes if applicable)
Add to cart

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IET Networks — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

© 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)
      • 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.
    2. 2)
      • 2. Malaguti, E., Toth, P.: ‘A survey on vertex coloring problems’, Int. Trans. Oper. Res., 2009, 17, (1), pp. 1–34.
    3. 3)
      • 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.
    4. 4)
      • 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.
    5. 5)
      • 5. Dias, B., de Freitasa, R., Maculan, N., et al: ‘Solving the bandwidth coloring problem applying constraint and integer programming techniques’, 2016.
    6. 6)
      • 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.
    7. 7)
      • 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.
    8. 8)
      • 8. Behzad, A., Rubin, Z.: ‘Multiple access protocol for power-controlled wireless access nets’, IEEE Trans. Mob. Comput., 2004, 3, (4), pp. 307–316.
    9. 9)
      • 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.
    10. 10)
      • 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.
    11. 11)
      • 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.
    12. 12)
      • 12. Xiangjing, L., Zhipeng, L.: ‘Multistart iterated tabu search for bandwidth coloring problem’, Comput. Oper. Res., 2013, 40, (5), pp. 1401–1409.
    13. 13)
      • 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.
    14. 14)
      • 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.
    15. 15)
      • 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.
    16. 16)
      • 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.
    17. 17)
      • 17. Johansson, O.: ‘Simple distributed (Δ+1)-coloring of graphs’, Inf. Process. Lett., 1999, 70, pp. 229–232.
    18. 18)
      • 18. Linial, N.: ‘Locality in distributed graph algorithms’, SIAM J. Comput., 1992, 21, (1), pp. 193–201.
    19. 19)
      • 19. Han, K., Kim, C.: ‘An evolutionary approach for graph multi-coloring problem’, Appl. Math. Sci., 2015, 9, (34), pp. 1677–1684.
    20. 20)
      • 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.
    21. 21)
      • 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.
    22. 22)
      • 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.
    23. 23)
      • 23. Tanenbaum, A.S.: ‘Computer networks’ (Prentice-Hall, Amsterdam, The Netherlands, 2011, 5th edn.).
    24. 24)
      • 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.
    25. 25)
      • 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.
    26. 26)
      • 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.
    27. 27)
      • 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.
    28. 28)
      • 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.
    29. 29)
      • 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.
    30. 30)
      • 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.
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
Print this page
This is a required field
Please enter a valid email address