Optimal short cycle decomposition in almost linear time

DOI10.4230/LIPICS.ICALP.2019.89MaRDI QIDQ5091249zbMATH OpenFDO

Authors Eylon Yogev, M. Parter

Publication date 21 July 2022

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2019.89

zbMATH Keywords

cycle decompositiongraph sparsificationlow-congestion cycle cover

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Recommendations

• Short cycles via low-diameter decompositions
• Breaking the O(m 2 n) Barrier for Minimum Cycle Bases
• Fast computation of small cuts via cycle space sampling
• Improved distributed expander decomposition and nearly optimal triangle enumeration
• Towards the Erdős-Gallai cycle decomposition conjecture

Cites work

• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Distributed Computing: A Locality-Sensitive Approach
• Efficient $\widetilde{O}(n/\epsilon)$ Spectral Sketches for the Laplacian and its Pseudoinverse
• scientific article; zbMATH DE number 3600081 (Why is no real title available?)
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• On sketching quadratic forms
• Towards resistance sparsifiers
• Twice-Ramanujan sparsifiers

Cited in

(5)

• Hardness of approximation in p via short cycle removal: cycle detection, distance oracles, and beyond
• Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions
• Maximum length-constrained flows and disjoint paths: distributed, deterministic, and fast
• Better sparsifiers for directed Eulerian graphs
• Invited talk: Resilient distributed algorithms

This page was built for publication: Optimal short cycle decomposition in almost linear time

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