Bibliography of distributed approximation beyond bounded degree.

Laurent Feuilloley

Bibliographic note. 2020. Updapted in December 2021.

Links

Arxiv

Abstract

This document is an informal bibliography of the papers dealing with distributed approximation algorithms. A classic setting for such algorithms is bounded degree graphs, but there is a whole set of techniques that have been developed for other classes. These later classes are the focus of the current work. These classes have a geometric nature (planar, bounded genus and unit-disk graphs) and/or have bounded parameters (arboricity, expansion, growth, independence) or forbidden structures (forbidden minors).

Notes

This document is meant to help the community, and is not designed to be published. Also it may evolve: any comment is most welcome. The original title was "Bibliography of distributed approximation for structurally sparse graph classes" but following the suggestion of a colleague I changed to the less obscure current title.