iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://unpaywall.org/10.1007/S11704-020-9205-Y
VColor*: a practical approach for coloring large graphs | Frontiers of Computer Science Skip to main content
Springer Nature Link
Log in

VColor*: a practical approach for coloring large graphs

  • Research Article
  • Published:
Frontiers of Computer Science Aims and scope Submit manuscript

This article has been updated

Abstract

Graph coloring has a wide range of real world applications, such as in the operations research, communication network, computational biology and compiler optimization fields. In our recent work [1], we propose a divide-and-conquer approach for graph coloring, called VColor. Such an approach has three generic subroutines. (i) Graph partition subroutine: VColor partitions a graph G into a vertex cut partition (VP), which comprises a vertex cut component (VCC) and small non-overlapping connected components (CCs). (ii) Component coloring subroutine: VColor colors the VCC and the CCs by efficient algorithms. (iii) Color combination subroutine: VColor combines the local colors by exploiting the maximum matchings of color combination bigraphs (CCBs). VColor has revealed some major bottlenecks of efficiency in these subroutines. Therefore, in this paper, we propose VColor*, an approach which addresses these efficiency bottlenecks without using more colors both theoretically and experimentally. The technical novelties of this paper are the following. (i) We propose the augmented VP to index the crossing edges of the VCC and the CCs and propose an optimized CCB construction algorithm. (ii) For sparse CCs, we propose using a greedy coloring algorithm that is of polynomial time complexity in the worst case, while preserving the approximation ratio. (iii) We propose a distributed graph coloring algorithm. Our extensive experimental evaluation on real-world graphs confirms the efficiency of VColor*. In particular, VColor* is 20X and 50X faster than VColor and uses the same number of colors with VColor on the Pokec and PA datasets, respectively. VColor* also significantly outperforms the state-of-the-art graph coloring methods.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Change history

  • 05 May 2021

    The corresponding author Yun Peng is incorrect, it should be Xin Lin.

References

  1. Peng Y, Choi B, He B, Zhou S, Xu R, Yu X. Vcolor: a practical vertex-cut based approach for coloring large graphs. In: Proceedings of IEEE International Conference on Data Engineering. 2016, 97–108

  2. Ingrid A. Nucleic acid sequence design as a graph colouring problem. Thesis, Universitat Wien, 2005, 1–83

  3. Park T, Lee C Y. Application of the graph coloring algorithm to the frequency assignment problem. Journal of the Operations Research of Japan, 1996, 39(2): 258–265

    MathSciNet  MATH  Google Scholar 

  4. Chaitin G. Register allocation and spilling via graph coloring. ACM Sigplan Notices, 1982, 17(6): 98–101

    Article  MathSciNet  Google Scholar 

  5. Lotfi V, Sarin S. A graph coloring algorithm for large scale scheduling problems. Computers & Operations Research, 1986, 13(1): 27–32

    Article  MathSciNet  Google Scholar 

  6. Moradi F, Olovsson T, Tsigas P. A local seed selection algorithm for overlapping community detection. In: Proceedings of IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. 2014, 1–8

  7. Yuan L, Qin L, Lin X, Chang L, Zhang W. Diversified top-k clique search. In: Proceedings of IEEE International Conference on Data Engineering. 2015, 387–398

  8. Hertz A, De Werra D. Using tabu search techniques for graph coloring. Computing, 1987, 39(4): 345–351

    Article  MathSciNet  Google Scholar 

  9. HalldÃşrsson M M. A still better performance guarantee for approximate graph coloring. Information Processing Letters, 1993, 45(1): 19–23

    Article  MathSciNet  Google Scholar 

  10. Galinier P, Hao J K. Hybrid evolutionary algorithms for graph coloring. Journal of Combinatorial Optimization, 1999, 3(4): 379–397

    Article  MathSciNet  Google Scholar 

  11. Galinier P, Hamiez J P, Hao J K, Porumbel D. Recent advances in graph vertex coloring. Handbook of Optimization, 2013, 1: 505–528

    Article  Google Scholar 

  12. Karger D, Motwani R, Sudan M. Approximate graph coloring by semidefinite programming. Journal of the ACM, 1998, 45(2): 246–265

    Article  MathSciNet  Google Scholar 

  13. Pardalos P M, Mavridou T, Xue J. The Graph Coloring Problem: a Bibliographic Survey. Handbook of Combinatorial Optimization, Springer, Boston, 1999, 1077–1141

  14. Husfeldt T. Graph Colouring Algorithms. Cambridge University Press, 2015, 277–303

  15. Kuhn F, Wattenhofer R. On the complexity of distributed graph coloring. In: Proceedings of ACM Symposium on Principles of Distributed Computing. 2006, 7–15

  16. Eppstein D. All maximal independent sets and dynamic dominance for sparse graphs. ACM Transactions on Algorithms, 2009, 5(4): 1–14

    Article  MathSciNet  Google Scholar 

  17. Byskov J M. Enumerating maximal independent sets with applications to graph colouring. Operations Research Letters, 2004, 32(6): 547–556

    Article  MathSciNet  Google Scholar 

  18. Feige U, Mahdian M. Finding small balanced separators. In: Proceedings of the Annual ACM Symposium on Theory of Computing. 2006, 375–384

  19. Johnson D J, Trick M A. Cliques, Coloring, and Satisfiability. Boston, MA, USA: American Mathematical Society, 1996

    Book  Google Scholar 

  20. Lee J, Han W S, Kasperovics R, Lee J H. An in-depth comparison of subgraph isomorphism algorithms in graph databases. Proceedings of the VLDB Endowment, 2012, 6(2): 133–144

    Article  Google Scholar 

  21. Jones M T, Plassmann P E. A parallel graph coloring heuristic. SIAM Journal on Scientific Computing, 1993, 14(3): 654–669

    Article  MathSciNet  Google Scholar 

  22. Salihoglu S, Widom J. Optimizing graph algorithms on pregel-like systems. Proceedings of the VLDB Endowment, 2014, 7(7): 577–588

    Article  Google Scholar 

  23. Yuan L, Qin L, Lin X, Chang L, Zhang W. Effective and efficient dynamic graphcoloring. Proceedings of the VLDB Endowment, 2017, 11(2): 338–351

    Article  Google Scholar 

  24. Barba L, Cardinal J, Korman M, Langerman S, Renssen V A, Roeloffzen M, Verdonschot S. Dynamic graph coloring. Algorithmica, 2019, 81(4): 1319–1341

    Article  MathSciNet  Google Scholar 

  25. Blöchliger I, Zufferey N. A graph coloring heuristic using partial solutions and a reactive tabu scheme. Computers & Operations Research, 2008, 35(3): 960–975

    Article  MathSciNet  Google Scholar 

  26. Porumbel D, Hao J K, Kuntz P. A study of evaluation functions for the graph k-coloring problem. Artificial Evolution, 2008, 1: 124–135

    Article  MathSciNet  Google Scholar 

  27. Hertz A, Plumettaz M, Zufferey N. Variable space search for graph coloring. Discrete Applied Mathematics, 2008, 156(13): 2551–2560

    Article  MathSciNet  Google Scholar 

  28. Morgenstern C, Shapiro H. Coloration neighborhood structures for general graph coloring. In: Proceedings of Annual ACM-SIAM Symposium on Discrete Algorithms. 1990, 226–235

  29. Fleurent C, Ferland J. Genetic and hybrid algorithms for graph coloring. Annals of Operations Research, 1996, 63(3): 437–461

    Article  Google Scholar 

  30. Galinier P, Hertz A, Zufferey N. An adaptive memory algorithm for the k-coloring problem. Discrete Applied Mathematics, 2008, 156(2): 267–279

    Article  MathSciNet  Google Scholar 

  31. Porumbel D C, Hao J K, Kuntz P. An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring. Computers & Operations Research, 2010, 37(10): 1822–1832

    Article  Google Scholar 

  32. Lü Z, Hao J K. A memetic algorithm for graph coloring. European Journal of Operational Research, 2010, 203(1): 241–250

    Article  MathSciNet  Google Scholar 

  33. Chams M, Hertz A, De Werra D. Some experiments with simulated annealing for coloring graphs. European Journal of Operational Research, 1987, 32(2): 260–266

    Article  MathSciNet  Google Scholar 

  34. Johnson D S, Aragon C R, McGeoch L A, Schevon C. Optimization by simulated annealing: an experimental evaluation; part ii, graph coloring and number partitioning. Operations Research, 1991, 39(3): 378–406

    Article  Google Scholar 

  35. Wu Q, Hao J K. Coloring large graphs based on independent set extraction. Computers & Operations Research, 2012, 39(2): 283–290

    Article  MathSciNet  Google Scholar 

  36. Wu Q, Hao J K. An extraction and expansion approach for graph coloring. Asia-Pacific Journal of Operational Research, 2013, 30(5): 1350018

    Article  MathSciNet  Google Scholar 

  37. Hao J K, Wu Q. Improving the extraction and expansion method for large graph coloring. Discrete Applied Mathematics, 2012, 160(16–17): 2397–2407

    Article  MathSciNet  Google Scholar 

  38. Schneider J, Wattenhofer R. A new technique for distributed symmetry breaking. In: Proceedings of ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing. 2010, 257–266

  39. Luby M. A simple parallel algorithm for the maximal independent set problem. In: Proceedings of Annual ACM Symposium on Theory of Computing. 1985, 1–10

  40. Cole R, Vishkin U. Deterministic coin tossing with applications to optimal parallel list ranking. Information and Control, 1986, 70(1): 32–53

    Article  MathSciNet  Google Scholar 

  41. Linial N. Locality in distributed graph algorithms. SIAM Journal on Computing, 1992, 21(1): 193–201

    Article  MathSciNet  Google Scholar 

  42. Szegedy M, Vishwanathan S. Locality based graph coloring. In: Proceedings of ACM Symposium on Theory of Computing. 1993, 201–207

  43. Panconesi A, Srinivasan A. On the Complexity of Distributed Network Decomposition. Academic Press, Inc., 1996

  44. Barenboim L, Elkin M, Kuhn F. Distributed (delta + 1)-coloring in linear (in delta) time. Siam Journal on Computing, 2014, 43(1): 72–95

    Article  MathSciNet  Google Scholar 

  45. Checco A, Leith D J. Fast, responsive decentralized graph coloring. IEEE/ACM Transactions on Networking, 2017, 25(6): 3628–3640

    Article  Google Scholar 

Download references

Acknowledgements

Thanks to the support of NSF of China (61773167, 61929103), NSF of Shandong Province (ZR2019LZH006), NSF of Shanghai (17ZR1444900, HKRGC GRF 12201119, 12232716 and 12201518), QLUT Young Scholar Program (2018DBSHZ005).

Author information

Authors and Affiliations

  1. Department of Computer Science, Hong Kong Baptist University, Hong Kong, 999077, China

    Yun Peng & Byron Choi

  2. School of Computer Science and Technology, East China Normal University, Shanghai, 200062, China

    Xin Lin

  3. School of Computing, National University of Singapore, Singapore, 119077, Singapore

    Bingsheng He

Authors
  1. Yun Peng
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xin Lin
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Byron Choi
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Bingsheng He
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Xin Lin.

Additional information

Yun Peng received the PhD degree from the Hong Kong Baptist University, China in 2013 and received the BSci and MPhil degrees in computer science from Shandong University and the Harbin Institute of Technology (HIT), China in 2006 and 2008, respectively. His research interests include graph-structured data processing, data mining and machine learning.

Xin Lin received the BEng and PhD degrees, both in computer science and engineering, from Zhejiang University, China. He is currently a professor in the Department of Computer Science and Technology, East China Normal University, China. His research interests include location-based services, spatial databases, privacy-aware computing, and crowdsourcing.

Byron Choi is an associate professor in the Department of Computer Science at the Hong Kong Baptist University, China. He received the bachelor of engineering degree in computer engineering from the Hong Kong University of Science and Technology (HKUST), China in 1999 and the MSE and PhD degrees in computer and information science from the University of Pennsylvania, USA in 2002 and 2006, respectively.

Bingsheng He received the bachelor degree in computer science from Shanghai Jiao Tong University (1999–2003), and the PhD degree in computer science in Hong Kong University of Science and Technology (2003–2008), China. He is an associate professor in School of Computing, National University of Singapore, Singapore. His research interests are high performance computing, distributed and parallel systems, and database systems.

Supporting Information

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Peng, Y., Lin, X., Choi, B. et al. VColor*: a practical approach for coloring large graphs. Front. Comput. Sci. 15, 154610 (2021). https://doi.org/10.1007/s11704-020-9205-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s11704-020-9205-y

Keywords

Search

Navigation