Aug 2026· 2026 International Conference on Emerging Techniques in Computational Intelligence (ICETCI)· pp. 1-8· 0 citations· 39 references
Abstract
This work proposes graph-aware hybrid approach that combines classical graph algorithms and Large Language Models (LLMs) to improve interpretability of the solutions for combinatorial optimization problems. The proposed framework is capable of solving such NP-hard problems as Traveling Salesman Problem (TSP), Graph Coloring, Maximum Clique, Minimum Vertex Cover and Hamiltonian Path using the optimization backend built with the use of FastAPI framework together with the LLM explanations and D3.js visualization. The proposed framework is evaluated using the datasets of TSPLIB, DIMACS and randomly generated graphs. The experimental results showed that TSP solver was able to find the solution that is 5.4% -14.5% far from the optimal tour length after 2-opt refinement, graph coloring is optimal in 4 out of 5 benchmarks and maximum clique is optimal in all evaluated datasets. Finally, the user experiment showed that LLM explanations can improve users' comprehension of the solutions without compromising the quality of the solutions.
This is the first study to employ an ensemble-based approach that combines multiple metaheuristics for solving the GCP in a parallel computing environment, and demonstrates substantial reductions in execution time, with near-linear scalability and speed-up.
Tansel Dokeroglu, Deniz Canturk· Journal of Data Science and...· 0 citations
The Double-Partition Coloring Problem (DPCP) is a recently introduced generalization of several coloring problems on graphs and hypergraphs, including the Partition Coloring Problem, the List Coloring Problem, and the Conflict-Free Coloring Problem (CFCP). In this work, we further investigate the structural and computa...
Mauro Lucci, G. Nasini, Paola B. Tolomei et al.· 0 citations
In interval graphs and many generalizations thereof, problems such as Matching, Independent Set, and Dominating Set can be solved with simple greedy algorithms in linear (i.e., $O(m+n)$) time. However, it is sometimes possible to improve on this runtime if a suitable representation as intersection graph is given; for e...
The Dual-GNN Multilevel Coarsening framework uses learning to guide multilevel graph coarsening while retaining combinatorial search for final decision making and achieves the best mean solution quality among all evaluated methods.
The Graph Coloring Problem (GCP) is NP-hard and DSATUR stands as one of the fastest heuristics for it despite producing colorings that typically use more colors than state-of-the-art coloring algorithms. We propose SSLD (Semidefinite Spectral Learning with DSATUR), which improves DSATUR by preprocessing a first good co...
The Quantum Approximate Optimization Algorithm (QAOA) is a near-term quantum algorithm for solving combinatorial optimization problems, but its accuracy and resource requirements may scale poorly with problem size or structure, reducing its utility in practice. Approaches such as the Graph Decomposition for Optimizatio...
M. Brunet, Leah Prepchuk, Rebekah Herrman· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.