Deterministic expander routing: faster and more versatile

DOI10.1145/3662158.3662797MaRDI QIDQ6971956zbMATH OpenFDO

Authors Yi-Jun Chang, Shang-En Huang, Hsin-Hao Su

Publication date 13 June 2025

Full work available at URL https://doi.org/10.1145/3662158.3662797

zbMATH Keywords

CONGESTMSTroutingsortingtriangle detection

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Cites work

• A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond
• A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction
• Computing cut-based hierarchical decompositions in almost linear time
• Detecting cliques in CONGEST networks
• Deterministic distributed expander decomposition and routing with applications in distributed derandomization
• Deterministic Near-Optimal Distributed Listing of Cliques
• Distributed data summarization in well-connected networks
• Distributed MST and routing in almost mixing time
• Distributed verification and hardness of distributed approximation
• Graph partitioning using single commodity flows
• Hop-constrained expander decompositions, oblivious routing, and distributed universal optimality
• scientific article; zbMATH DE number 7561283 (Why is no real title available?)
• scientific article; zbMATH DE number 7650908 (Why is no real title available?)
• scientific article; zbMATH DE number 7829267 (Why is no real title available?)
• scientific article; zbMATH DE number 7788509 (Why is no real title available?)
• scientific article; zbMATH DE number 7788631 (Why is no real title available?)
• Maximum length-constrained flows and disjoint paths: distributed, deterministic, and fast
• Near-optimal Distributed Triangle Enumeration via Expander Decompositions
• Near-optimal scheduling of distributed algorithms
• On Distributed Listing of Cliques
• On the complexity of local distributed graph problems
• Packet routing and job-shop scheduling in \(O\) (congestion + dilation) steps
• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• Sublinear-Time Parallel Algorithms for Matching and Related Problems
• Triangle Finding and Listing in CONGEST Networks
• Universally-optimal distributed algorithms for known topologies

Cited in

(1)

• Narrowing the \textsf{LOCAL-CONGEST} gaps in sparse networks via expander decompositions

This page was built for publication: Deterministic expander routing: faster and more versatile

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