Back to Search
Start Over
Parallel Computing Aspects in Improved Edge Cover Based Graph Coloring Algorithm
- Source :
- Indian Journal of Science and Technology. 10:1-9
- Publication Year :
- 2017
- Publisher :
- Indian Society for Education and Environment, 2017.
-
Abstract
- 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.
- Subjects :
- Matching (graph theory)
Computer science
Dinic's algorithm
Parallel algorithm
02 engineering and technology
Parallel computing
Floyd–Warshall algorithm
Edge cover
Greedy coloring
030507 speech-language pathology & audiology
03 medical and health sciences
Ramer–Douglas–Peucker algorithm
Graph power
0202 electrical engineering, electronic engineering, information engineering
Graph coloring
Time complexity
Sequential algorithm
Blossom algorithm
FSA-Red Algorithm
List coloring
Hopcroft–Karp algorithm
Multidisciplinary
Graph
Vertex (geometry)
Edge coloring
Graph bandwidth
Independent set
Reverse-delete algorithm
020201 artificial intelligence & image processing
Johnson's algorithm
Suurballe's algorithm
Fractional coloring
0305 other medical science
Subjects
Details
- ISSN :
- 09745645 and 09746846
- Volume :
- 10
- Database :
- OpenAIRE
- Journal :
- Indian Journal of Science and Technology
- Accession number :
- edsair.doi...........72895b0dd5b37baf448595e6e7e977fb