As Editor-in-Chief of The Computer Journal, published by Oxford University Press on behalf of BCS, The Chartered Institute for IT, it is my honour to select the recipient of the annual Wilkes Award, awarded to the authors of the best paper published in the previous year’s volume. The key judging criteria for the Award are originality and quality of theme and treatment, as assessed by an expert judging panel.
We are pleased to announce this year’s winning and runner-up papers for the 2025 Wilkes Award for Volume 67 (2024):
Winning paper
Approximation algorithms for maximum weighted internal spanning trees in regular graphs and subdivisions of graphs
Sheikh Azizul Hakim, Rahnuma Islam Nishat and Md. Saidur Rahman
The Computer Journal, Volume 67, Issue 10 (October 2024), pp.2898-2905
https://doi.org/10.1093/comjnl/bxae055
This paper addresses the Maximum Weighted Internal Spanning Tree (MaxwIST) problem: given a vertex-weighted graph, find a spanning tree that maximises the combined weight of its internal vertices. The unweighted version is NP-complete, since a Hamiltonian path is the spanning tree with the fewest possible leaves, and the weighted version inherits this hardness. Prior work had given good approximation guarantees for cubic, three-regular, graphs specifically; this paper generalises that line of work to any fixed regular degree, with a fast algorithm whose guarantee improves as the degree grows, and proves a matching upper bound by constructing graphs for which no spanning tree can do much better. The authors then extend the approach to subdivisions of these graphs, where edges are replaced by chains of extra degree-two vertices, a setting not previously studied systematically despite its relevance to physical and logical network infrastructure, deriving algorithms for subdivided regular, Hamiltonian and related graph classes whose guarantees approach the optimum as the subdivisions get longer. Experiments on thousands of randomly generated regular graphs show the algorithm performing considerably better in practice than its worst-case guarantee. The combination of a generalised algorithm, a matching hardness construction, and the first systematic treatment of subdivided graph classes makes for a thorough, well-evidenced extension of the literature, and a worthy winner of this year’s Award.
Runner-up
Dynamic compact data structure for temporal reachability with unsorted contact insertions
Luiz Fernando Afra Brito, Marcelo Keese Albertini, Bruno Augusto Nassif Travençolo and Gonzalo Navarro
The Computer Journal, Volume 67, Issue 10 (October 2024), pp.2984-2994
https://doi.org/10.1093/comjnl/bxae063
This paper tackles a practical bottleneck in maintaining reachability information for temporal graphs, where interactions between entities arrive over time and may need to be processed in any order rather than strict chronological sequence, a setting relevant to applications such as tracking epidemic spread. The authors’ own earlier work had solved this by maintaining, for every pair of vertices, a balanced binary search tree of time intervals, but the space these trees require grows quickly as more interactions are recorded, so here they replace each tree with a more compact pair of dynamic bit-vectors, offering two variants, one storing bits explicitly for speed and one encoding only the gaps between set bits for space, along with a new operation that keeps the space-efficient variant just as fast to update as the original tree-based approach. Experiments show the new structure can use substantially less memory than the original, particularly at the sparse and dense ends of the density range tested, generally at a modest cost in running time. It is a focused, incremental contribution, a more compact and nearly as fast replacement for the authors’ own earlier reachability structure, of the kind that quietly extends how large a temporal graph can be kept in memory.
You can browse previous winners of the Wilkes Award, and find out more about the Award itself. Thank you also to the 2025 Wilkes Award judging panel:
- Professor Chris Mitchell, Royal Holloway, University of London, UK
- Professor Jim Woodcock, University of York, UK
- Nicky Danino, Leeds Trinity University, UK
The award is named after Sir Maurice Wilkes (1913-2010), Director of the Cambridge University Computer Laboratory from 1945 to 1980, throughout the development of stored program computers starting with EDSAC, which ran the first realistic programs on a stored-program electronic computer in 1949. He went on to invent microprogramming, and, with David Wheeler and Stanley Gill, developed an early programming system based on subroutines and labels that shaped how software was written for decades afterwards. Wilkes was also the founding President of the British Computer Society (1957-60), received the ACM A.M. Turing Award in 1967, and was knighted for his services to computing in 2000.
Digital Society & Policy 