Parallel Computing Aspects in Improved Edge Cover Based Graph Coloring Algorithm Article Swipe

PDF

Harish Patidar , Prąsun Chakrabarti , Amrit Ghosh ·

YOU? · · 2017 · Open Access · · DOI: https://doi.org/10.17485/ijst/2017/v10i25/115117

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. Keywords: Edge Cover, Graph Coloring, Independent Set, Multithreading, Parallel Computing, Vertex Coloring

Related Topics

Computer Science

Algorithm

Graph Coloring

Floyd–Warshall Algorithm

Theoretical Computer Science

Dijkstra's Algorithm

Line Graph

Concepts

Computer science Algorithm Graph coloring Floyd–Warshall algorithm Greedy coloring Edge coloring Graph Theoretical computer science Graph power Shortest path problem Dijkstra's algorithm Line graph

Metadata

Type: article
Language: en
Landing Page: https://doi.org/10.17485/ijst/2017/v10i25/115117
PDF: http://www.indjst.org/index.php/indjst/article/download/115117/80823
OA Status: diamond
Cited By: 1
References: 13
Related Works: 10
OpenAlex ID: https://openalex.org/W2734866571

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W2734866571

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.17485/ijst/2017/v10i25/115117

Digital Object Identifier
Title: Parallel Computing Aspects in Improved Edge Cover Based Graph Coloring Algorithm

Work title
Type: article

OpenAlex work type
Language: en

Primary language
Publication year: 2017

Year of publication
Publication date: 2017-02-01

Full publication date if available
Authors: Harish Patidar, Prąsun Chakrabarti, Amrit Ghosh

List of authors in order
Landing page: https://doi.org/10.17485/ijst/2017/v10i25/115117

Publisher landing page
PDF URL: https://www.indjst.org/index.php/indjst/article/download/115117/80823

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: diamond

Open access status per OpenAlex
OA URL: https://www.indjst.org/index.php/indjst/article/download/115117/80823

Direct OA link when available
Concepts: Computer science, Algorithm, Graph coloring, Floyd–Warshall algorithm, Greedy coloring, Edge coloring, Graph, Theoretical computer science, Graph power, Shortest path problem, Dijkstra's algorithm, Line graph

Top concepts (fields/topics) attached by OpenAlex
Cited by: 1

Total citation count in OpenAlex
Citations by year (recent): 2023: 1

Per-year citation counts (last 5 years)
References (count): 13

Number of works referenced by this work
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W2734866571
doi	https://doi.org/10.17485/ijst/2017/v10i25/115117
ids.doi	https://doi.org/10.17485/ijst/2017/v10i25/115117
ids.mag	2734866571
ids.openalex	https://openalex.org/W2734866571
fwci	0.0
type	article
title	Parallel Computing Aspects in Improved Edge Cover Based Graph Coloring Algorithm
biblio.issue	25
biblio.volume	10
biblio.last_page	9
biblio.first_page	1
topics[0].id	https://openalex.org/T10374
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9926000237464905
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1703
topics[0].subfield.display_name	Computational Theory and Mathematics
topics[0].display_name	Advanced Graph Theory Research
topics[1].id	https://openalex.org/T12401
topics[1].field.id	https://openalex.org/fields/18
topics[1].field.display_name	Decision Sciences
topics[1].score	0.9916999936103821
topics[1].domain.id	https://openalex.org/domains/2
topics[1].domain.display_name	Social Sciences
topics[1].subfield.id	https://openalex.org/subfields/1803
topics[1].subfield.display_name	Management Science and Operations Research
topics[1].display_name	Scheduling and Timetabling Solutions
topics[2].id	https://openalex.org/T12541
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.9905999898910522
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/1703
topics[2].subfield.display_name	Computational Theory and Mathematics
topics[2].display_name	Graph Labeling and Dimension Problems
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C41008148
concepts[0].level	0
concepts[0].score	0.772672176361084
concepts[0].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[0].display_name	Computer science
concepts[1].id	https://openalex.org/C11413529
concepts[1].level	1
concepts[1].score	0.6388832330703735
concepts[1].wikidata	https://www.wikidata.org/wiki/Q8366
concepts[1].display_name	Algorithm
concepts[2].id	https://openalex.org/C76946457
concepts[2].level	3
concepts[2].score	0.5867723822593689
concepts[2].wikidata	https://www.wikidata.org/wiki/Q504843
concepts[2].display_name	Graph coloring
concepts[3].id	https://openalex.org/C186065694
concepts[3].level	5
concepts[3].score	0.4561549723148346
concepts[3].wikidata	https://www.wikidata.org/wiki/Q1047576
concepts[3].display_name	Floyd–Warshall algorithm
concepts[4].id	https://openalex.org/C38767284
concepts[4].level	5
concepts[4].score	0.4163796901702881
concepts[4].wikidata	https://www.wikidata.org/wiki/Q5601715
concepts[4].display_name	Greedy coloring
concepts[5].id	https://openalex.org/C123809776
concepts[5].level	5
concepts[5].score	0.41477176547050476
concepts[5].wikidata	https://www.wikidata.org/wiki/Q1050972
concepts[5].display_name	Edge coloring
concepts[6].id	https://openalex.org/C132525143
concepts[6].level	2
concepts[6].score	0.3623597323894501
concepts[6].wikidata	https://www.wikidata.org/wiki/Q141488
concepts[6].display_name	Graph
concepts[7].id	https://openalex.org/C80444323
concepts[7].level	1
concepts[7].score	0.23390230536460876
concepts[7].wikidata	https://www.wikidata.org/wiki/Q2878974
concepts[7].display_name	Theoretical computer science
concepts[8].id	https://openalex.org/C149530733
concepts[8].level	4
concepts[8].score	0.19434243440628052
concepts[8].wikidata	https://www.wikidata.org/wiki/Q5597091
concepts[8].display_name	Graph power
concepts[9].id	https://openalex.org/C22590252
concepts[9].level	3
concepts[9].score	0.19099414348602295
concepts[9].wikidata	https://www.wikidata.org/wiki/Q1058754
concepts[9].display_name	Shortest path problem
concepts[10].id	https://openalex.org/C173870130
concepts[10].level	4
concepts[10].score	0.18981075286865234
concepts[10].wikidata	https://www.wikidata.org/wiki/Q8548
concepts[10].display_name	Dijkstra's algorithm
concepts[11].id	https://openalex.org/C203776342
concepts[11].level	3
concepts[11].score	0.14007213711738586
concepts[11].wikidata	https://www.wikidata.org/wiki/Q1378376
concepts[11].display_name	Line graph
keywords[0].id	https://openalex.org/keywords/computer-science
keywords[0].score	0.772672176361084
keywords[0].display_name	Computer science
keywords[1].id	https://openalex.org/keywords/algorithm
keywords[1].score	0.6388832330703735
keywords[1].display_name	Algorithm
keywords[2].id	https://openalex.org/keywords/graph-coloring
keywords[2].score	0.5867723822593689
keywords[2].display_name	Graph coloring
keywords[3].id	https://openalex.org/keywords/floyd–warshall-algorithm
keywords[3].score	0.4561549723148346
keywords[3].display_name	Floyd–Warshall algorithm
keywords[4].id	https://openalex.org/keywords/greedy-coloring
keywords[4].score	0.4163796901702881
keywords[4].display_name	Greedy coloring
keywords[5].id	https://openalex.org/keywords/edge-coloring
keywords[5].score	0.41477176547050476
keywords[5].display_name	Edge coloring
keywords[6].id	https://openalex.org/keywords/graph
keywords[6].score	0.3623597323894501
keywords[6].display_name	Graph
keywords[7].id	https://openalex.org/keywords/theoretical-computer-science
keywords[7].score	0.23390230536460876
keywords[7].display_name	Theoretical computer science
keywords[8].id	https://openalex.org/keywords/graph-power
keywords[8].score	0.19434243440628052
keywords[8].display_name	Graph power
keywords[9].id	https://openalex.org/keywords/shortest-path-problem
keywords[9].score	0.19099414348602295
keywords[9].display_name	Shortest path problem
keywords[10].id	https://openalex.org/keywords/dijkstras-algorithm
keywords[10].score	0.18981075286865234
keywords[10].display_name	Dijkstra's algorithm
keywords[11].id	https://openalex.org/keywords/line-graph
keywords[11].score	0.14007213711738586
keywords[11].display_name	Line graph
language	en
locations[0].id	doi:10.17485/ijst/2017/v10i25/115117
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S2764746358
locations[0].source.issn	0974-5645, 0974-6846
locations[0].source.type	journal
locations[0].source.is_oa	True
locations[0].source.issn_l	0974-5645
locations[0].source.is_core	True
locations[0].source.is_in_doaj	False
locations[0].source.display_name	Indian Journal of Science and Technology
locations[0].source.host_organization	https://openalex.org/P4322615647
locations[0].source.host_organization_name	Indian Society for Education and Environment
locations[0].source.host_organization_lineage	https://openalex.org/P4322615647
locations[0].source.host_organization_lineage_names	Indian Society for Education and Environment
locations[0].license	cc-by
locations[0].pdf_url	http://www.indjst.org/index.php/indjst/article/download/115117/80823
locations[0].version	publishedVersion
locations[0].raw_type	journal-article
locations[0].license_id	https://openalex.org/licenses/cc-by
locations[0].is_accepted	True
locations[0].is_published	True
locations[0].raw_source_name	Indian Journal of Science and Technology
locations[0].landing_page_url	https://doi.org/10.17485/ijst/2017/v10i25/115117
indexed_in	crossref
authorships[0].author.id	https://openalex.org/A5021636962
authorships[0].author.orcid
authorships[0].author.display_name	Harish Patidar
authorships[0].countries	IN
authorships[0].affiliations[0].institution_ids	https://openalex.org/I94511900
authorships[0].affiliations[0].raw_affiliation_string	Department of Computer Science and Engineering, Sir Padampat Singhania University, Udaipur – 313601, Rajasthan
authorships[0].institutions[0].id	https://openalex.org/I94511900
authorships[0].institutions[0].ror	https://ror.org/03mhsvf98
authorships[0].institutions[0].type	education
authorships[0].institutions[0].lineage	https://openalex.org/I94511900
authorships[0].institutions[0].country_code	IN
authorships[0].institutions[0].display_name	Sir Padampat Singhania University
authorships[0].author_position	first
authorships[0].raw_author_name	Harish Patidar
authorships[0].is_corresponding	False
authorships[0].raw_affiliation_strings	Department of Computer Science and Engineering, Sir Padampat Singhania University, Udaipur – 313601, Rajasthan
authorships[1].author.id	https://openalex.org/A5089771051
authorships[1].author.orcid	https://orcid.org/0000-0001-8062-4144
authorships[1].author.display_name	Prąsun Chakrabarti
authorships[1].countries	IN
authorships[1].affiliations[0].institution_ids	https://openalex.org/I94511900
authorships[1].affiliations[0].raw_affiliation_string	Department of Computer Science and Engineering, Sir Padampat Singhania University, Udaipur – 313601, Rajasthan
authorships[1].institutions[0].id	https://openalex.org/I94511900
authorships[1].institutions[0].ror	https://ror.org/03mhsvf98
authorships[1].institutions[0].type	education
authorships[1].institutions[0].lineage	https://openalex.org/I94511900
authorships[1].institutions[0].country_code	IN
authorships[1].institutions[0].display_name	Sir Padampat Singhania University
authorships[1].author_position	middle
authorships[1].raw_author_name	Prasun Chakrabarti
authorships[1].is_corresponding	False
authorships[1].raw_affiliation_strings	Department of Computer Science and Engineering, Sir Padampat Singhania University, Udaipur – 313601, Rajasthan
authorships[2].author.id	https://openalex.org/A5064400831
authorships[2].author.orcid	https://orcid.org/0000-0001-5162-2262
authorships[2].author.display_name	Amrit Ghosh
authorships[2].countries	IN
authorships[2].affiliations[0].institution_ids	https://openalex.org/I94511900
authorships[2].affiliations[0].raw_affiliation_string	Department of Computer Science and Engineering, Sir Padampat Singhania University, Udaipur – 313601, Rajasthan
authorships[2].institutions[0].id	https://openalex.org/I94511900
authorships[2].institutions[0].ror	https://ror.org/03mhsvf98
authorships[2].institutions[0].type	education
authorships[2].institutions[0].lineage	https://openalex.org/I94511900
authorships[2].institutions[0].country_code	IN
authorships[2].institutions[0].display_name	Sir Padampat Singhania University
authorships[2].author_position	last
authorships[2].raw_author_name	Amrit Ghosh
authorships[2].is_corresponding	False
authorships[2].raw_affiliation_strings	Department of Computer Science and Engineering, Sir Padampat Singhania University, Udaipur – 313601, Rajasthan
has_content.pdf	True
has_content.grobid_xml	True
is_paratext	False
open_access.is_oa	True
open_access.oa_url	http://www.indjst.org/index.php/indjst/article/download/115117/80823
open_access.oa_status	diamond
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Parallel Computing Aspects in Improved Edge Cover Based Graph Coloring Algorithm
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T03:46:38.306776
primary_topic.id	https://openalex.org/T10374
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9926000237464905
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1703
primary_topic.subfield.display_name	Computational Theory and Mathematics
primary_topic.display_name	Advanced Graph Theory Research
related_works	https://openalex.org/W4291316360, https://openalex.org/W1542397451, https://openalex.org/W3169197204, https://openalex.org/W4311345810, https://openalex.org/W2380525562, https://openalex.org/W2793500002, https://openalex.org/W4297911588, https://openalex.org/W4229747356, https://openalex.org/W2365437454, https://openalex.org/W2385428710
cited_by_count	1
counts_by_year[0].year	2023
counts_by_year[0].cited_by_count	1
locations_count	1
best_oa_location.id	doi:10.17485/ijst/2017/v10i25/115117
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S2764746358
best_oa_location.source.issn	0974-5645, 0974-6846
best_oa_location.source.type	journal
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l	0974-5645
best_oa_location.source.is_core	True
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	Indian Journal of Science and Technology
best_oa_location.source.host_organization	https://openalex.org/P4322615647
best_oa_location.source.host_organization_name	Indian Society for Education and Environment
best_oa_location.source.host_organization_lineage	https://openalex.org/P4322615647
best_oa_location.source.host_organization_lineage_names	Indian Society for Education and Environment
best_oa_location.license	cc-by
best_oa_location.pdf_url	http://www.indjst.org/index.php/indjst/article/download/115117/80823
best_oa_location.version	publishedVersion
best_oa_location.raw_type	journal-article
best_oa_location.license_id	https://openalex.org/licenses/cc-by
best_oa_location.is_accepted	True
best_oa_location.is_published	True
best_oa_location.raw_source_name	Indian Journal of Science and Technology
best_oa_location.landing_page_url	https://doi.org/10.17485/ijst/2017/v10i25/115117
primary_location.id	doi:10.17485/ijst/2017/v10i25/115117
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S2764746358
primary_location.source.issn	0974-5645, 0974-6846
primary_location.source.type	journal
primary_location.source.is_oa	True
primary_location.source.issn_l	0974-5645
primary_location.source.is_core	True
primary_location.source.is_in_doaj	False
primary_location.source.display_name	Indian Journal of Science and Technology
primary_location.source.host_organization	https://openalex.org/P4322615647
primary_location.source.host_organization_name	Indian Society for Education and Environment
primary_location.source.host_organization_lineage	https://openalex.org/P4322615647
primary_location.source.host_organization_lineage_names	Indian Society for Education and Environment
primary_location.license	cc-by
primary_location.pdf_url	http://www.indjst.org/index.php/indjst/article/download/115117/80823
primary_location.version	publishedVersion
primary_location.raw_type	journal-article
primary_location.license_id	https://openalex.org/licenses/cc-by
primary_location.is_accepted	True
primary_location.is_published	True
primary_location.raw_source_name	Indian Journal of Science and Technology
primary_location.landing_page_url	https://doi.org/10.17485/ijst/2017/v10i25/115117
publication_date	2017-02-01
publication_year	2017
referenced_works	https://openalex.org/W1544252245, https://openalex.org/W1885577394, https://openalex.org/W2044258347, https://openalex.org/W1975521444, https://openalex.org/W6659380759, https://openalex.org/W6668512682, https://openalex.org/W2071114738, https://openalex.org/W1973582947, https://openalex.org/W2382079786, https://openalex.org/W2035773351, https://openalex.org/W2100061495, https://openalex.org/W2138792657, https://openalex.org/W2073025989
referenced_works_count	13
abstract_inverted_index.75	78
abstract_inverted_index.It	191
abstract_inverted_index.To	1, 82
abstract_inverted_index.be	196
abstract_inverted_index.by	14, 95
abstract_inverted_index.in	19, 41, 61, 91, 109, 118
abstract_inverted_index.is	25, 44, 55, 73, 93, 98, 107, 136, 163, 176
abstract_inverted_index.of	27, 31, 89, 144, 174, 185, 188, 201
abstract_inverted_index.on	75, 100, 165
abstract_inverted_index.to	57, 68
abstract_inverted_index.100	158
abstract_inverted_index.and	46, 112, 130, 169
abstract_inverted_index.are	66, 150
abstract_inverted_index.but	160
abstract_inverted_index.can	195
abstract_inverted_index.for	121, 153, 198
abstract_inverted_index.not	151
abstract_inverted_index.one	26
abstract_inverted_index.set	13
abstract_inverted_index.the	3, 28, 84, 145, 182
abstract_inverted_index.Edge	4, 204
abstract_inverted_index.Java	49, 52
abstract_inverted_index.Most	143
abstract_inverted_index.Set,	209
abstract_inverted_index.Test	105
abstract_inverted_index.This	36, 124, 179
abstract_inverted_index.also	126
abstract_inverted_index.data	106
abstract_inverted_index.high	170
abstract_inverted_index.less	137
abstract_inverted_index.main	29
abstract_inverted_index.many	166
abstract_inverted_index.more	76
abstract_inverted_index.rate	173
abstract_inverted_index.some	39
abstract_inverted_index.test	69
abstract_inverted_index.than	77, 140, 157
abstract_inverted_index.that	114, 132
abstract_inverted_index.this	32, 110, 193
abstract_inverted_index.time	23, 85, 88, 120, 138
abstract_inverted_index.type	187
abstract_inverted_index.used	56, 67, 197
abstract_inverted_index.(more	156
abstract_inverted_index.Cover	5
abstract_inverted_index.Graph	7, 206
abstract_inverted_index.based	6
abstract_inverted_index.data.	190
abstract_inverted_index.exact	146
abstract_inverted_index.found	113, 131
abstract_inverted_index.graph	64, 80, 103, 147, 155
abstract_inverted_index.large	122, 154, 167
abstract_inverted_index.means	192
abstract_inverted_index.paper	37, 111, 125, 180
abstract_inverted_index.shows	181
abstract_inverted_index.types	200
abstract_inverted_index.using	11, 48
abstract_inverted_index.Cover,	205
abstract_inverted_index.DIMACS	63, 79, 102
abstract_inverted_index.ECGCA.	42
abstract_inverted_index.Vertex	213
abstract_inverted_index.graphs	168
abstract_inverted_index.paper.	33
abstract_inverted_index.tested	47, 74, 99, 164
abstract_inverted_index.(ECGCA)	10
abstract_inverted_index.Finding	21
abstract_inverted_index.achieve	58
abstract_inverted_index.analyze	83, 108
abstract_inverted_index.aspects	18
abstract_inverted_index.complex	139
abstract_inverted_index.concept	54
abstract_inverted_index.graphs.	123
abstract_inverted_index.improve	2
abstract_inverted_index.maximum	199
abstract_inverted_index.optimum	22, 119
abstract_inverted_index.results	184
abstract_inverted_index.seconds	92
abstract_inverted_index.success	172
abstract_inverted_index.Coloring	8, 214
abstract_inverted_index.Finding:	71
abstract_inverted_index.Parallel	211
abstract_inverted_index.coloring	148
abstract_inverted_index.compared	127
abstract_inverted_index.executed	117
abstract_inverted_index.parallel	16, 59, 128, 134
abstract_inverted_index.program.	96
abstract_inverted_index.proposed	115, 133, 161
abstract_inverted_index.suitable	152
abstract_inverted_index.Algorithm	9, 43, 72, 97
abstract_inverted_index.Analysis:	35
abstract_inverted_index.Coloring,	207
abstract_inverted_index.Keywords:	203
abstract_inverted_index.achieved.	177
abstract_inverted_index.algorithm	90, 116, 129, 135, 162, 175, 194
abstract_inverted_index.computing	17, 60
abstract_inverted_index.different	101, 186
abstract_inverted_index.execution	87, 171
abstract_inverted_index.instances	65
abstract_inverted_index.language.	51
abstract_inverted_index.vertices)	159
abstract_inverted_index.Computing,	212
abstract_inverted_index.Objective:	0
abstract_inverted_index.algorithm.	20, 62, 70, 142
abstract_inverted_index.algorithms	149
abstract_inverted_index.calculated	94
abstract_inverted_index.complexity	24
abstract_inverted_index.instances.	81, 104
abstract_inverted_index.introduced	38
abstract_inverted_index.objectives	30
abstract_inverted_index.sequential	141
abstract_inverted_index.Independent	208
abstract_inverted_index.application	189
abstract_inverted_index.complexity,	86
abstract_inverted_index.implemented	45
abstract_inverted_index.independent	12
abstract_inverted_index.programming	50
abstract_inverted_index.Application:	178
abstract_inverted_index.experimental	183
abstract_inverted_index.modification	40
abstract_inverted_index.applications.	202
abstract_inverted_index.incorporating	15
abstract_inverted_index.multithreading	53
abstract_inverted_index.Multithreading,	210
abstract_inverted_index.Methods/Statistical	34
cited_by_percentile_year.max	94
cited_by_percentile_year.min	89
countries_distinct_count	1
institutions_distinct_count	3
citation_normalized_percentile.value	0.11292464
citation_normalized_percentile.is_in_top_1_percent	False
citation_normalized_percentile.is_in_top_10_percent	False