Vertex Ordering Algorithms for Graph Coloring Problem

被引：0

作者：

Kaya, Kamer ^{[1
]}

Demirel, Berker ^{[1
]}

Topal, Baris Batuhan ^{[1
]}

Asik, Arda ^{[1
]}

Demir, Ibrahim Bugra ^{[1
]}

机构：

[1] Sabanci Univ, Istanbul, Turkey

来源：

2020 28TH SIGNAL PROCESSING AND COMMUNICATIONS APPLICATIONS CONFERENCE (SIU) | 2020年

关键词：

Graph coloring; greedy algorithms; closeness centrality;

D O I：

10.1109/siu49456.2020.9302296

中图分类号：

TM [电工技术]; TN [电子技术、通信技术];

学科分类号：

0808 ; 0809 ;

摘要：

Graph coloring is a fundamental problem in combinatorics with many applications in practice. In this problem, the vertices in a given graph must be colored by using the least number of colors in such a way that a vertex has a different color than its neighbors. The problem, as well as its different variants, have been proven to be NP-Hard. Therefore, there are greedy algorithms in the literature aiming to use a small number of colors. These algorithms traverse the vertices and color them one by one. The vertex visit order has a significant impact on the number of colors used. In this work, we investigated if social network analytics metrics can be used to find this order. Our experiments showed that when closeness centrality is used to find vertex visit order, a smaller number of colors is used by the greedy algorithms.

引用

收藏

页数：4

相关论文

共 50 条

[11] Population-based and Learning-based Metaheuristic Algorithms for the Graph Coloring Problem [J].

Chalupa, David .

GECCO-2011: PROCEEDINGS OF THE 13TH ANNUAL GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, 2011, :465-472

[12] Comparative Analysis of the main Graph Coloring Algorithms [J].

Postigo, Juan ;

Soto-Begazo, Juan ;

Villarroel, Fiorela R. ;

Picha, Gleddynuri M. ;

Flores-Quispe, Roxana ;

Velazco-Paredes, Yuber .

2021 IEEE COLOMBIAN CONFERENCE ON COMMUNICATIONS AND COMPUTING (COLCOM), 2021,

[13] Graph Coloring in a Class of Parallel Local Algorithms [J].

Evstigneev, V. A. ;

Kyzy, Y. Tursunbay .

NUMERICAL ANALYSIS AND APPLICATIONS, 2011, 4 (03) :189-198

[14] Efficient graph coloring with parallel genetic algorithms [J].

Kokosinski, Z ;

Kwarciany, K ;

Kolodziej, M .

COMPUTING AND INFORMATICS, 2005, 24 (02) :123-147

[15] Fully dynamic algorithms for permutation graph coloring [J].

Ivkovic, Z ;

Sarnath, R ;

Sunder, S .

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 1997, 63 (1-2) :37-55

[16] NEW APPROXIMATION ALGORITHMS FOR GRAPH-COLORING [J].

BLUM, A .

JOURNAL OF THE ACM, 1994, 41 (03) :470-516

[17] Linear Time Algorithms for Happy Vertex Coloring Problems for Trees [J].

Aravind, N. R. ;

Kalyanasundaram, Subrahmanyam ;

Kare, Anjeneya Swami .

COMBINATORIAL ALGORITHMS, 2016, 9843 :281-292

[18] An analysis of solution properties of the graph coloring problem [J].

Hamiez, JP ;

Hao, JK .

METAHEURISTICS: COMPUTER DECISION-MAKING, 2004, 86 :325-345

[19] The Coloring Reconfiguration Problem on Specific Graph Classes [J].

Hatanaka, Tatsuhiko ;

Ito, Takehiro ;

Zhou, Xiao .

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2019, E102D (03) :423-429

[20] A distribution evolutionary algorithm for the graph coloring problem [J].

Xu, Yongjian ;

Cheng, Huabin ;

Xu, Ning ;

Chen, Yu ;

Xie, Chengwang .

SWARM AND EVOLUTIONARY COMPUTATION, 2023, 80

← 1 2 3 4 5 →