Local density and its distributed approximation

DOI10.4230/LIPICS.STACS.2025.25MaRDI QIDQ7287759zbMATH OpenFDO

Authors Aleksander B. G. Christiansen, Ivor van der Hoog, Eva Rotenberg

Publication date 24 June 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2025.25

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• Adaptive out-orientations with applications
• Convergence to lexicographically optimal base in a (contra)polymatroid and applications to densest subgraph and tree packing
• Dense subgraphs on dynamic networks
• Deterministic distributed edge-coloring via hypergraph maximal matching
• Distributed degree splitting, edge coloring, and orientations
• Distributed dense subgraph detection and low outdegree orientation
• Distributed local approximation algorithms for maximum matching in graphs and hypergraphs
• Egalitarian graph orientations
• Fair Integral Network Flows
• Fully dynamic MIS in uniformly sparse graphs
• Fully-dynamic + 2 Arboricity decompositions and implicit colouring
• scientific article; zbMATH DE number 2185626 (Why is no real title available?)
• Improved dynamic colouring of sparse graphs
• Lexicographically Optimal Base of a Polymatroid with Respect to a Weight Vector
• Maximum length-constrained flows and disjoint paths: distributed, deterministic, and fast
• Near-optimal fully dynamic densest subgraph
• On derandomizing local distributed algorithms
• Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
• Stochastic matching on uniformly sparse graphs

Cited in

(1)

• From theory to practice: engineering approximation algorithms for dynamic orientation

This page was built for publication: Local density and its distributed approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7287759)