DIAMOND: a distributed algorithm for vertex coloring problems and resource allocation
DIAMOND: a distributed algorithm for vertex coloring problems and resource allocation
- Author(s): Mohammadhasan Miri 1 ; Kamal Mohamedpour 1 ; Yousef Darmani 1 ; Mahasweta Sarkar 2
- DOI: 10.1049/iet-net.2018.5204
For access to this article, please select a purchase option:
Buy article PDF
Buy Knowledge Pack
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.
Thank you
Your recommendation has been sent to your librarian.
- Author(s): Mohammadhasan Miri 1 ; Kamal Mohamedpour 1 ; Yousef Darmani 1 ; Mahasweta Sarkar 2
-
-
View affiliations
-
Affiliations:
1:
Department of ECE , K.N. Toosi University of Technology , Tehran , Iran ;
2: Department of ECE , San Diego State University , San Diego , USA
-
Affiliations:
1:
Department of ECE , K.N. Toosi University of Technology , Tehran , Iran ;
- Source:
Volume 8, Issue 6,
November
2019,
p.
381 – 389
DOI: 10.1049/iet-net.2018.5204 , Print ISSN 2047-4954, Online ISSN 2047-4962
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)
-
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)
-
11. Kothapalli, K., Scheideler, C., Onus, M., et al: ‘Distributed coloring in O~(logn) bit rounds’. Proc. 20th IEEE Int. Parallel and Distributed Processing Symp., Rhodes Island, 2006, vol. 24, (3), p. 10.
-
-
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)
-
5. Dias, B., de Freitasa, R., Maculan, N., et al: ‘Solving the bandwidth coloring problem applying constraint and integer programming techniques’, 2016.
-
-
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)
-
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)
-
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)
-
18. Linial, N.: ‘Locality in distributed graph algorithms’, SIAM J. Comput., 1992, 21, (1), pp. 193–201.
-
-
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)
-
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)
-
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)
-
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)
-
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)
-
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)
-
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)
-
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)
-
12. Xiangjing, L., Zhipeng, L.: ‘Multistart iterated tabu search for bandwidth coloring problem’, Comput. Oper. Res., 2013, 40, (5), pp. 1401–1409.
-
-
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)
-
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)
-
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)
-
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)
-
2. Malaguti, E., Toth, P.: ‘A survey on vertex coloring problems’, Int. Trans. Oper. Res., 2009, 17, (1), pp. 1–34.
-
-
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)
-
17. Johansson, O.: ‘Simple distributed (Δ+1)-coloring of graphs’, Inf. Process. Lett., 1999, 70, pp. 229–232.
-
-
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)
-
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)
-
19. Han, K., Kim, C.: ‘An evolutionary approach for graph multi-coloring problem’, Appl. Math. Sci., 2015, 9, (34), pp. 1677–1684.
-
-
28)
-
23. Tanenbaum, A.S.: ‘Computer networks’ (Prentice-Hall, Amsterdam, The Netherlands, 2011, 5th edn.).
-
-
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)
-
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.
-
-
1)

Related content
