Abstract
Graph coloring is a fundamental graph problem that is widely applied in a variety of applications. The aim of graph coloring is to minimize the number of colors used to color the vertices in a graph such that no two incident vertices have the same color. Existing solutions for graph coloring mainly focus on computing a good coloring for a static graph. However, since many real-world graphs are highly dynamic, in this paper, we aim to incrementally maintain the graph coloring when the graph is dynamically updated. We target on two goals: high effectiveness and high efficiency. To achieve high effectiveness, we maintain the graph coloring in a way such that the coloring result is consistent with one of the best static graph coloring algorithms for large graphs. To achieve high efficiency, we investigate efficient incremental algorithms to update the graph coloring by exploring a small number of vertices. We design a color-propagation based algorithm which only explores the vertices within the 2-hop neighbors of the update-related and color-changed vertices. We then propose a novel color index to maintain some summary color information and, thus, bound the explored vertices within the neighbors of these vertices. Moreover, we derive some effective pruning rules to further reduce the number of propagated vertices. The experimental results demonstrate the high effectiveness and efficiency of our approach.
- A. Aboulnaga, J. Xiang, and C. Guo. Scalable maximum clique computation using mapreduce. In Proceedings of ICDE, pages 74--85, 2013. Google ScholarDigital Library
- D. Alberts, G. Cattaneo, and G. F. Italiano. An empirical study of dynamic graph algorithms. Journal of Experimental Algorithmics (JEA), 2:5, 1997. Google ScholarDigital Library
- N. Armenatzoglou, H. Pham, V. Ntranos, D. Papadias, and C. Shahabi. Real-time multi-criteria social graph partitioning: A game theoretic approach. In Proceedings of SIGMOD, pages 1617--1628, 2015. Google ScholarDigital Library
- C. Avanthay, A. Hertz, and N. Zufferey. A variable neighborhood search for graph coloring. European Journal of Operational Research, 151(2):379--388, 2003.Google ScholarCross Ref
- B. Balasundaram and S. Butenko. Graph domination, coloring and cliques in telecommunications. In Handbook of Optimization in Telecommunications, pages 865--890. Springer, 2006.Google ScholarCross Ref
- N. Barnier and P. Brisset. Graph coloring for air traffic flow management. Annals of operations research, 130(1):163--178, 2004.Google Scholar
- I. Blöchliger and N. Zufferey. A graph coloring heuristic using partial solutions and a reactive tabu scheme. Computers & Operations Research, 35(3):960--975, 2008. Google ScholarDigital Library
- É. Bonnet, F. Foucaud, E. J. Kim, and F. Sikora. Complexity of grundy coloring and its variants. In International Computing and Combinatorics Conference, pages 109--120, 2015.Google Scholar
- P. Borowiecki and E. Sidorowicz. Dynamic coloring of graphs. Fundamenta Informaticae, 114(2):105--128, 2012. Google ScholarDigital Library
- J. Boyar, L. M. Favrholdt, C. Kudahl, K. S. Larsen, and J. W. Mikkelsen. Online algorithms with advice: A survey. ACM Computing Surveys (CSUR), 50(2):19, 2017. Google ScholarDigital Library
- D. Brélaz. New methods to color the vertices of a graph. Communications of the ACM, 22(4):251--256, 1979. Google ScholarDigital Library
- E. Burjons, J. Hromkovič, X. Muñoz, and W. Unger. Online graph coloring with advice and randomized adversary. In International Conference on Current Trends in Theory and Practice of Informatics, pages 229--240, 2016. Google ScholarDigital Library
- I. Caragiannis, A. V. Fishkin, C. Kaklamanis, and E. Papaioannou. A tight bound for online colouring of disk graphs. Theoretical Computer Science, 384(2-3):152--160, 2007. Google ScholarDigital Library
- A. Carroll, G. Heiser, et al. An analysis of power consumption in a smartphone. In USENIX annual technical conference, pages 21--21, 2010. Google ScholarDigital Library
- M. Chiarandini, T. Stützle, et al. An application of iterated local search to graph coloring problem. In Proceedings of the Computational Symposium on Graph Coloring and its Generalizations, pages 112--125, 2002.Google Scholar
- C. A. Christen and S. M. Selkow. Some perfect coloring properties of graphs. Journal of Combinatorial Theory, Series B, 27(1):49--59, 1979.Google ScholarCross Ref
- D. Costa and A. Hertz. Ants can colour graphs. Journal of the operational research society, 48(3):295--305, 1997.Google Scholar
- J. C. Culberson and F. Luo. Exploring the k-colorable landscape with iterated greedy. Cliques, coloring, and satisfiability: second DIMACS implementation challenge, 26:245--284, 1996.Google Scholar
- C. Demetrescu, D. Eppstein, Z. Galil, and G. F. Italiano. Dynamic graph algorithms. In Algorithms and theory of computation handbook, pages 9--28, 2010. Google ScholarDigital Library
- R. Dorne and J.-K. Hao. A new genetic local search algorithm for graph coloring. In International Conference on Parallel Problem Solving from Nature, pages 745--754, 1998. Google ScholarDigital Library
- R. G. Downey and C. McCartin. Online promise problems with online width metrics. Journal of Computer and System Sciences, 73(1):57--72, 2007. Google ScholarDigital Library
- K. A. Dowsland and J. M. Thompson. An improved ant colony optimisation heuristic for graph colouring. Discrete Applied Mathematics, 156(3):313--324, 2008. Google ScholarDigital Library
- A. Dutot, F. Guinand, D. Olivier, and Y. Pigné. On the decentralized dynamic graph coloring problem. In Workshop of COSSOM, 2007.Google Scholar
- W. Erben. A grouping genetic algorithm for graph colouring and exam timetabling. In International Conference on the Practice and Theory of Automated Timetabling, pages 132--156, 2000. Google ScholarDigital Library
- W. Fan, X. Wang, and Y. Wu. Querying big graphs within bounded resources. In Proceedings of SIGMOD, pages 301--312, 2014. Google ScholarDigital Library
- P. Galinier and J.-K. Hao. Hybrid evolutionary algorithms for graph coloring. Journal of combinatorial optimization, 3(4):379--397, 1999.Google Scholar
- M. R. Garey and D. S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1990. Google ScholarDigital Library
- A. H. Gebremedhin, D. Nguyen, M. M. A. Patwary, and A. Pothen. Colpack: Software for graph coloring and related problems in scientific computing. ACM Transactions on Mathematical Software, 40(1):1, 2013. Google ScholarDigital Library
- A. Gyárfás and J. Lehel. On-line and first fit colorings of graphs. Journal of Graph theory, 12(2):217--227, 1988.Google ScholarCross Ref
- M. M. Halldórsson. Parallel and on-line graph coloring. Journal of Algorithms, 23(2):265--280, 1997. Google ScholarDigital Library
- M. M. Halldórsson and M. Szegedy. Lower bounds for on-line graph coloring. In Proceedings of SODA, pages 211--216, 1992. Google ScholarDigital Library
- F. Havet and L. Sampaio. On the grundy number of a graph. In International Symposium on Parameterized and Exact Computation, pages 170--179, 2010.Google ScholarCross Ref
- S. M. Hedetniemi, S. T. Hedetniemi, and T. Beyer. A linear algorithm for the grundy (coloring) number of a tree. Congr. Numer, 36:351--363, 1982.Google Scholar
- A. Hertz and D. de Werra. Using tabu search techniques for graph coloring. Computing, 39(4):345--351, 1987. Google ScholarDigital Library
- A. Hertz, M. Plumettaz, and N. Zufferey. Variable space search for graph coloring. Discrete Applied Mathematics, 156(13):2551--2560, 2008. Google ScholarDigital Library
- X. Huang, H. Cheng, L. Qin, W. Tian, and J. X. Yu. Querying k-truss community in large and dynamic graphs. In Proceedings of SIGMOD, pages 1311--1322, 2014. Google ScholarDigital Library
- D. S. Johnson, C. R. Aragon, L. A. McGeoch, and C. Schevon. Optimization by simulated annealing: an experimental evaluation; part ii, graph coloring and number partitioning. Operations research, 39(3):378--406, 1991.Google ScholarCross Ref
- H. A. Kierstead, D. A. Smith, and W. T. Trotter. First-fit coloring on interval graphs has performance ratio at least 5. European Journal of Combinatorics, 51:236--254, 2016. Google ScholarDigital Library
- H. A. Kierstead and W. T. Trotter. An extremal problem in recursive combinatorics. Congressus Numerantium, 33(143--153):98, 1981.Google Scholar
- S. M. Korman. The graph-colouring problem. Combinatorial optimization, pages 211--235, 1979.Google Scholar
- M. Laguna and R. Martí. A grasp for coloring sparse graphs. Computational optimization and applications, 19(2):165--178, 2001. Google ScholarDigital Library
- R. Lewis. A general-purpose hill-climbing method for order independent minimum grouping problems: A case study in graph colouring and bin packing. Computers & Operations Research, 36(7):2295--2310, 2009. Google ScholarDigital Library
- R. Lewis, J. Thompson, C. Mumford, and J. Gillard. A wide-ranging computational comparison of high-performance graph colouring algorithms. Computers & Operations Research, 39(9):1933--1950, 2012. Google ScholarDigital Library
- L. Lovász, M. Saks, and W. T. Trotter. An on-line graph coloring algorithm with sublinear performance ratio. Discrete Mathematics, 75(1-3):319--325, 1989. Google ScholarDigital Library
- Z. Lü and J.-K. Hao. A memetic algorithm for graph coloring. European Journal of Operational Research, 203(1):241--250, 2010.Google ScholarCross Ref
- E. Malaguti, M. Monaci, and P. Toth. A metaheuristic approach for the vertex coloring problem. INFORMS Journal on Computing, 20(2):302--316, 2008. Google ScholarDigital Library
- J. Manweiler and R. Roy Choudhury. Avoiding the rush hours: Wifi energy management via traffic isolation. In Proceedings of MobiSys, pages 253--266, 2011. Google ScholarDigital Library
- D. W. Matula and L. L. Beck. Smallest-last ordering and clustering and graph coloring algorithms. Journal of the ACM, 30(3):417--427, 1983. Google ScholarDigital Library
- F. Moradi, T. Olovsson, and P. Tsigas. A local seed selection algorithm for overlapping community detection. In Proceedings of ASONAM, pages 1--8, 2014.Google ScholarCross Ref
- C. Morgenstern. Distributed coloration neighborhood search. Discrete Mathematics and Theoretical Computer Science, 26:335--358, 1996.Google ScholarCross Ref
- A. Mukherjee and M. Hansen. A dynamic rerouting model for air traffic flow management. Transportation Research Part B: Methodological, 43(1):159--171, 2009.Google ScholarCross Ref
- C. L. Mumford. New order-based crossovers for the graph coloring problem. In Parallel Problem Solving from Nature-PPSN IX, pages 880--889. 2006. Google ScholarDigital Library
- N. Narayanaswamy and R. S. Babu. A note on first-fit coloring of interval graphs. Order, 25(1):49--53, 2008.Google ScholarCross Ref
- N. Ohsaka, T. Maehara, and K.-i. Kawarabayashi. Efficient pagerank tracking in evolving networks. In Proceedings of KDD, pages 875--884, 2015. Google ScholarDigital Library
- P. R. J. Östergård. A fast algorithm for the maximum clique problem. Discrete Appl. Math., 120(1-3):197--207, 2002. Google ScholarDigital Library
- L. Ouerfelli and H. Bouziri. Greedy algorithms for dynamic graph coloring. In Proceedings of CCCA, pages 1--5, 2011.Google ScholarCross Ref
- Y. Peng, B. Choi, B. He, S. Zhou, R. Xu, and X. Yu. Vcolor: A practical vertex-cut based approach for coloring large graphs. In Proceedings of ICDE, pages 97--108, 2016.Google ScholarCross Ref
- D. C. Porumbel, J.-K. Hao, and P. Kuntz. An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring. Computers & Operations Research, 37(10):1822--1832, 2010. Google ScholarDigital Library
- S. Prestwich. Using an incomplete version of dynamic backtracking for graph colouring. Electronic Notes in Discrete Mathematics, 1:61--73, 1999.Google ScholarCross Ref
- D. Preuveneers and Y. Berbers. Acodygra: an agent algorithm for coloring dynamic graphs. Symbolic and Numeric Algorithms for Scientific Computing, 6:381--390, 2004.Google Scholar
- R. A. Rossi and N. K. Ahmed. Coloring large complex networks. Social Network Analysis and Mining, 4(1):228, 2014.Google ScholarCross Ref
- C. Schindelhauer. Mobility in wireless networks. In International Conference on Current Trends in Theory and Practice of Computer Science, pages 100--116, 2006. Google ScholarDigital Library
- S. Smorodinsky. A note on the online first-fit algorithm for coloring k-inductive graphs. Information Processing Letters, 109(1):44--45, 2008. Google ScholarDigital Library
- B. C. Steffen. Advice complexity of online graph problems. Ph.D Thesis, 2014.Google Scholar
- Z. Tang, B. Wu, L. Hu, and M. Zaker. More bounds for the grundy number of graphs. Journal of Combinatorial Optimization, 33(2):580--589, 2017. Google ScholarDigital Library
- J. A. Telle and A. Proskurowski. Algorithms for vertex partitioning problems on partial k-trees. SIAM Journal on Discrete Mathematics, 10(4):529--550, 1997. Google ScholarDigital Library
- S. Vishwanathan. Randomized online graph coloring. In Proceedings of FOCS, pages 464--469, 1990. Google ScholarDigital Library
- D. J. Welsh and M. B. Powell. An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal, 10(1):85--86, 1967.Google ScholarCross Ref
- Q. Wu and J.-K. Hao. Coloring large graphs based on independent set extraction. Computers & Operations Research, 39(2):283--290, 2012. Google ScholarDigital Library
- L. Yuan, L. Qin, X. Lin, L. Chang, and W. Zhang. Diversified top-k clique search. In Proceedings of ICDE, pages 387--398, 2015.Google ScholarCross Ref
- M. Zaker. Results on the grundy chromatic number of graphs. Discrete mathematics, 306(23):3166-3173, 2006. Google ScholarDigital Library
- D. Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. In Proceedings of STOC, pages 681--690, 2006. Google ScholarDigital Library
Index Terms
- Effective and efficient dynamic graph coloring
Recommendations
Graph edge colouring: Tashkinov trees and Goldberg's conjecture
For the chromatic index @g^'(G) of a (multi)graph G, there are two trivial lower bounds, namely the maximum degree @D(G) and the density W(G)=max"H"@__ __"G","|"V"("H")"|">="2@__ __|E(H)|/@__ __|V(H)|/2@__ __@__ __. A famous conjecture due to Goldberg [...
Dynamic Coloring on Restricted Graph Classes
Algorithms and ComplexityAbstractA proper k-coloring of a graph is an assignment of colors from the set to the vertices of the graph such that no two adjacent vertices receive the same color. Given a graph , the Dynamic Coloring problem asks to find a proper k-coloring of G such ...
Comments