Fast distributed algorithms for girth, cycles and small subgraphs

DOI10.4230/LIPICS.DISC.2020.33MaRDI QIDQ6535032zbMATH OpenFDO

Authors Keren Censor-Hillel, Orr Fischer, Tzlil Gonen, François Le Gall, Dean Leitersdorf, Rotem Oshman

Publication date 2 November 2023

Full work available at URL https://doi.org/10.4230/LIPICS.DISC.2020.33

zbMATH Keywords

CONGESTcongested cliquecyclesdistributed graph algorithmsgirth

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Recommendations

• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• scientific article; zbMATH DE number 7053319

Cites work

• ``Tri, tri again: finding triangles and small subgraphs in a distributed setting (extended abstract)
• Approximating the girth
• Color-coding
• Deterministic subgraph detection in broadcast CONGEST
• Distributed algorithms for network diameter and girth
• Distributed coloring algorithms for triangle-free graphs
• Distributed triangle detection via expander decomposition
• Efficient approximation algorithms for shortest cycles in undirected graphs
• Fast Approximate Shortest Paths in the Congested Clique
• Finding a Minimum Circuit in a Graph
• Finding and counting given length cycles
• Further algebraic algorithms in the congested clique model and applications to graph-theoretic problems
• scientific article; zbMATH DE number 7053319 (Why is no real title available?)
• Improved distributed expander decomposition and nearly optimal triangle enumeration
• Large cuts with local algorithms on triangle-free graphs
• Minimum Weight Cycles and Triangles: Equivalences and Algorithms
• Networks cannot compute their diameter in sublinear time
• On the power of the congested clique model
• Optimal deterministic routing and sorting on the congested clique
• Optimal distributed all pairs shortest paths and applications
• Sparse matrix multiplication and triangle listing in the congested clique model
• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• The distributed minimum spanning tree problem
• The history of degenerate (bipartite) extremal graph problems
• Triangle Finding and Listing in CONGEST Networks

Cited in

(10)

• Fast diameter computation within split graphs
• On the power of threshold-based algorithms for detecting cycles in the \textsc{CONGEST} model
• On the power of threshold-based algorithms for detecting cycles in the CONGEST model
• Deterministic near-optimal distributed listing of cliques
• Improved all-pairs approximate shortest paths in congested clique
• Even-cycle detection in the randomized and quantum CONGEST model
• Computing minimum weight cycle in the CONGEST model
• Distributed subgraph finding: progress and challenges (invited talk)
• Improved all-pairs approximate shortest paths in congested clique
• String problems in the congested clique model

This page was built for publication: Fast distributed algorithms for girth, cycles and small subgraphs

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