Edge-colored Clustering in Hypergraphs: A MaxECC Approximation

Graph Coloring Algorithms and Their Applications in Combinatorial Optimization: A Survey

Coloring the vertices, edges or faces of a graph so that no two adjacent elements share a label is among the oldest problems in graph theory, and one of the few whose reach extends into exam timetables and wireless spectrum allocation as it does into pure combinatorics. This survey draws together the problem’s theoretical core – vertex, edge, face, list and total coloring – with the algorithms built to solve it and the industries that now depend on those algorithms. Because coloring is NP-hard, we trace the field’s progression from exact and greedy methods (Welsh-Powell, DSATUR, backtracking) through metaheuristics that trade optimality for scale (genetic algorithms, tabu search, simulated annealing, ant colony and artificial bee colony optimization), to the graph neural network and quantum-inspired solvers that have emerged in recent years. Rather than treating theory, algorithms and applications as separate literatures, we connect them directly: each application – examination and crew scheduling, frequency assignment, compiler register allocation, cartographic map coloring – is traced back to the specific coloring variant and algorithm family the literature actually uses, while the algorithm families themselves are compared head-to-head on complexity, solution quality and scalability rather than catalogued one at a time. This comparative structure, together with its coverage of recent learning-based solvers, is what distinguishes this survey from the standard references on the subject. We close by outlining where the field’s open problems remain, from long standing conjectures to the still-unanswered question of whether learned heuristics can match classical methods at real-world scale.

Small boundary: a family of linear-time greedy heuristics for the minimum linear arrangement problem

This paper addresses the minimum linear arrangement problem, a classical graph layout problem in which the objective is to minimize the sum of absolute differences between the labels assigned to adjacent vertices in undirected graphs. The paper introduces small boundary (SB(k)), a family of linear-time greedy heuristics that guide vertex labeling through a prioritization scheme based on the structure of labeled and k levels of unlabeled vertex neighborhoods. An extensive experimental evaluation on 26 large-scale real-world graphs demonstrates that the proposed heuristic with k=2 consistently outperforms 19 established low-cost graph-theoretic reordering algorithms, including the leading constructive method used within a high-performing metaheuristic algorithm for the problem. Additionally, the SB(2) heuristic outperforms this high-performing metaheuristic algorithm while requiring up to 800 times less computational effort. The paper further shows that integrating SB(2) as the initialization procedure within this metaheuristic yields improved solution quality, highlighting its effectiveness as both a standalone heuristic and a high-quality initializer. Overall, the proposed approach provides a fast, scalable, and practical solution for tackling MinLA on large-scale graphs.

On the Best Interval Approximation Problem

This paper generalises the existing PTAS for complete graphs from a fixed to an arbitrary number of intervals and disprove an existing conjecture, which states that every instance of BIA admits a solution satisfying at least three quarters of all edges.

Online and Incremental Fractional Vertex Cover on Trees

In this paper we study the fractional vertex cover problem on trees in two related models: online and incremental. In the online model, the vertices of the tree are known a priori and the edges arrive one at a time. The goal is to maintain a fractional vertex cover of the tree, i.e., an assignment of fractional weights from [0,1] to the vertices such that the weights of endpoints of every edge sum up to at least one. After each edge arrival, we need to modify the fractional vertex cover to cover the new edge as well. However, we can only increase the values assigned to vertices. The problem was studied before (in the vertex arrival model) by Wang and Wong, who motivated it as a generalization of the ski-rental problem, but also (more importantly) by its close connection to the dual online matching problem. They presented a 1.901-competitive algorithm for general graphs in the vertex arrival model. We present an $\frac{11}{6} \approx 1.83$-competitive algorithm for trees in the more general edge arrival model. In addition, we study the fractional vertex cover problem in an incremental model, where we again seek a fractional vertex cover after every update, but all the updates to the tree are known to the algorithm a priori. In this model, we give a 1.5-competitive algorithm and provide a matching lower bound.

Partially-Dynamic Maximum Flow in Dense Graphs

Parameterized and Streaming Algorithms for Euclidean Fair k -Center Clustering