An experimental evaluation of upper bounds of clique weights based on graph coloring
- Resource Type
- Conference
- Authors
- Kashihara, Yuki; Yamaguchi, Kazuaki; Nakamura, Masahide
- Source
- 2023 IEEE/ACIS 8th International Conference on Big Data, Cloud Computing, and Data Science (BCD) Big Data, Cloud Computing, and Data Science (BCD), 2023 IEEE/ACIS 8th International Conference on. :222-230 Dec, 2023
- Subject
- Communication, Networking and Broadcast Technologies
Components, Circuits, Devices and Systems
Computing and Processing
Engineering Profession
Robotics and Control Systems
Cloud computing
Upper bound
Data science
Big Data
component
formatting
style
styling
insert
- Language
- ISSN
- 2835-4419
The maximum weighted clique problem is the problem to find the clique whose sum of weights is maximum in vertex-weighted graphs. A branch and bound algorithm is often used to solve this problem. A branch and bound algorithm solves the subproblems recursively to find the exact solution and can be faster by pruning subproblems which cannot improve the incumbent solution according to the upper bound. Greedy coloring is often used to find the upper bound of the maximum weighted clique problem. The coloring depends on vertex ordering and this affects the upper bound. In this paper, we propose an algorithm to obtain vertex ordering by using the smallest last ordering. We compared the proposed algorithm with a conventional method through some computational experiments using random graphs. Experimental results show that the proposed algorithm can get the exact solution faster than others for some sparse graphs.