Total views : 52

Parallel Computing Aspects in Improved Edge Cover Based Graph Coloring Algorithm


  • Department of Computer Science and Engineering, Sir Padampat Singhania University, Udaipur – 313601, Rajasthan, India


Objective: To improve the Edge Cover based Graph Coloring Algorithm (ECGCA) using independent set by incorporating parallel computing aspects in algorithm. Finding optimum time complexity is one of the main objectives of this paper. Methods/Statistical Analysis: This paper introduced some modification in ECGCA. Algorithm is implemented and tested using Java programming language. Java multithreading concept is used to achieve parallel computing in algorithm. DIMACS graph instances are used to test algorithm. Finding: Algorithm is tested on more than 75 DIMACS graph instances. To analyze the time complexity, execution time of algorithm in seconds is calculated by program. Algorithm is tested on different DIMACS graph instances. Test data is analyze in this paper and found that proposed algorithm executed in optimum time for large graphs. This paper also compared parallel algorithm and found that proposed parallel algorithm is less time complex than sequential algorithm. Most of the exact graph coloring algorithms are not suitable for large graph (more than 100 vertices) but proposed algorithm is tested on many large graphs and high execution success rate of algorithm is achieved. Application: This paper shows the experimental results of different type of application data. It means this algorithm can be used for maximum types of applications.


Edge Cover, Graph Coloring, Independent Set, Multithreading, Parallel Computing, Vertex Coloring.

Full Text:

 |  (PDF views: 36)


  • Gandhi NM, Misra R. Performance comparison of parallel graph coloring algorithms on BSP model using hadoop. Proceeding of International Conference on Computing Networking and Communications (ICNC); USA; 2015. p. 110–6. Crossref
  • Duan F, Lei Y, Yu L, Kachker RN and Kuhn DR. Improving IPOG’s vertical growth based on a graph coloring scheme. Proceeding of 8th International Conference on Software Testing Verification and Validation Workshops (ICSTW); Austria; 2015. p. 1–8. Crossref
  • Stecke K. Design planning, scheduling and control problems of flexible manufacturing systems. Annals of Operations Research. 1985 Jan; 3(1):1–12. Crossref
  • Camino JT, Mourgues S, Artigues C, Houssin L. A greedy approach combined with graph coloring for non-uniform beam layouts under antenna constraints in multibeam satellite systems. Proceeding of 7th Advanced Satellite Multimedia Systems Conference (ASMS) and 13th Signal Processing for Space Communications Workshop (SPSC); Italy; 2014. p. 374–81. Crossref
  • Barnier N, Brisset P. Graph coloring for air traffic flow management. Annals of Operations Research. 2004 Aug; 130(1):163–78. Crossref
  • Robson JM. Algorithms for maximum independent sets. Journal of Algorithms. 1986 Sep; 7(3):425–40. Crossref
  • Luby M. A simple parallel algorithm for the maximal independent set problem. SIAM Journal on Computing. 1986 Nov; 15(4):1036–53. Crossref
  • Krivelevich M, Nathaniel R, Sudakov B. Approximating coloring and maximum independent sets in 3-uniform hypergraphs. Journal of Algorithms. 2001 Oct; 41(1):99– 113. Crossref
  • The Independent Set Algorithm [Internet]. 2006 [updated 2006; cited 2017 Mar 3]. Available from:
  • Keil J. Mark, Mitchell J, Pradhan D, Vatshell M. An algorithm for the maximum weight independent set problem on outerstring graphs. Proceeding of 27th Conference on Computational Geometry; Canada. 2016 May; 60:19–25.
  • A family of greedy algorithms for finding maximum independent set [Internet]. 2015 [updated 2015 May 4; cited 2017 Mar 17]. Available from:
  • Accelerating local search for the maximum independent set problem [Internet]. 2016 [updated 2016 Feb 4; cited 2017 Mar 17]. Available from:


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.