Fast distributed algorithms for girth, cycles and small subgraphs
From MaRDI portal
Publication:6535032
DOI10.4230/lipics.disc.2020.33zbMATH Open1540.68301MaRDI QIDQ6535032
Tzlil Gonen, Keren Censor-Hillel, François Le Gall, Rotem Oshman, Dean Leitersdorf, Orr Fischer
Publication date: 2 November 2023
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Distributed algorithms (68W15)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding and counting given length cycles
- Efficient approximation algorithms for shortest cycles in undirected graphs
- Further algebraic algorithms in the congested clique model and applications to graph-theoretic problems
- Algebraic methods in the congested clique
- Sparse matrix multiplication and triangle listing in the congested clique model
- Distributed coloring algorithms for triangle-free graphs
- Large cuts with local algorithms on triangle-free graphs
- Approximating the Girth
- Optimal distributed all pairs shortest paths and applications
- On the power of the congested clique model
- Distributed Algorithms for Network Diameter and Girth
- Deterministic Subgraph Detection in Broadcast CONGEST.
- Finding a Minimum Circuit in a Graph
- Color-coding
- “Tri, Tri Again”: Finding Triangles and Small Subgraphs in a Distributed Setting
- Improved Distributed Expander Decomposition and Nearly Optimal Triangle Enumeration
- Fast Approximate Shortest Paths in the Congested Clique
- Optimal deterministic routing and sorting on the congested clique
- Distributed Triangle Detection via Expander Decomposition
- Triangle Finding and Listing in CONGEST Networks
- The History of Degenerate (Bipartite) Extremal Graph Problems
- Minimum Weight Cycles and Triangles: Equivalences and Algorithms
- Sublinear-time distributed algorithms for detecting small cliques and even cycles
Related Items (2)
Fast diameter computation within split graphs ⋮ Deterministic near-optimal distributed listing of cliques
This page was built for publication: Fast distributed algorithms for girth, cycles and small subgraphs
