VColor^(*):a practical approach for coloring large graphs

作     者：Yun PENG Xin LIN Byron CHOI Bingsheng HE Yun PENG;Xin LIN;Byron CHOI;Bingsheng HE

作者机构：Department of Computer ScienceHong Kong Baptist UniversityHong Kong 999077China School of Computer Science and TechnologyEast China Normal UniversityShanghai 200062China School of ComputingNational University of SingaporeSingapore 119077Singapore 

出 版 物：《Frontiers of Computer Science》 (中国计算机科学前沿（英文版）)

年 卷 期：2021年第15卷第4期

页      面：133-149页

核心收录：

学科分类：081203[工学-计算机应用技术] 08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：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) 

主　　题：graph coloring approximation algorithm distributed algorithm 

摘      要：Graph coloring has a wide range of real world applications,such as in the operations research,communication network,computational biology and compiler optimization *** our recent work[1],we propose a divide-andconquer approach for graph coloring,called *** 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 ***,in this paper,we propose VColor^(*),an approach which addresses these efficiency bottlenecks without using more colors both theoretically and *** 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 *** 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,***^(*)also significantly outperforms the state-ofthe-art graph coloring methods.