Advances in Graph Algorithms and Distributed Computing

The field of graph algorithms and distributed computing is witnessing significant developments, with a focus on improving approximation ratios, designing efficient algorithms for dynamic graphs, and developing local certification schemes. Researchers are exploring new techniques, such as combining primal-dual algorithms with submodular maximization, to achieve better approximation guarantees for classic problems like Steiner Forest. Additionally, there is a growing interest in dynamic graphs, with studies on monotone decontamination and maintaining proper colorings on temporal graphs. The use of mobile agents is also being investigated for solving fundamental graph problems in distributed settings. Noteworthy papers include: Steiner Forest: A Simplified Better-Than-2 Approximation, which improves the approximation ratio for the Steiner Forest problem. Constant-Size Certificates for Leader Election in Chordal Graphs and Related Classes, which presents local certification schemes for leader election and spanning tree construction in specific graph classes. Improved Linear-Time Construction of Minimal Dominating Set via Mobile Agents, which achieves a linear-time solution for computing a minimal dominating set in anonymous graphs using mobile agents.

Sources

Approximating maximum properly colored forests via degree bounded independent sets

Monotone Decontamination of Arbitrary Dynamic Graphs with Mobile Agents

Steiner Forest: A Simplified Better-Than-2 Approximation

Constant-Size Certificates for Leader Election in Chordal Graphs and Related Classes

Improved Linear-Time Construction of Minimal Dominating Set via Mobile Agents

Maintaining Bipartite Colourings on Temporal Graphs on a Budget

Enumeration With Nice Roman Domination Properties

Built with on top of