Researchers have developed a near-optimal algorithm that colors the edges of a graph in nearly linear time.
Graph edges represent the paths that planes can take at an airport, for example, with vertices representing points such as gates and runways, and colours indicating times or other attributes.
The so-called graph edge colouring problem is important in computer science, software engineering, and in the analysis of networks such as airport traffic.
Although they are heavily used, algorithms for colouring the edges of a graph have not changed significantly in the past 40 years.
Two advancements last year reduced the time it took to colour a graph to the number of edges multiplied by the cube or fourth root of the number of vertices, but the new ‘nearly optimal’ algorithm brings the time down to the logarithm of the number of edges.
Researchers are now trying to produce a version that doesn’t use randomisation and achieves linear – rather than near-linear – time.
