Low-congestion shortcut and graph parameters

DOI10.1007/s00446-021-00401-xOpenAlexW2982448703MaRDI QIDQ2241301

Yota Otachi, Taisuke Izumi, Hirotaka Kitagawa, Naoki Kitamura

Publication date: 8 November 2021

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1908.09473

zbMATH Keywords

minimum spanning treeclique widthdistributed graph algorithms\(k\)-chordal graphlow-congestion shortcut

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• New hash functions and their use in authentication and set equality
• Near-linear lower bounds for distributed distance computations, even in sparse networks
• Near-optimal low-congestion shortcuts on bounded parameter graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction
• Near-Optimal Scheduling of Distributed Algorithms
• An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
• Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• Fast Distributed Construction of Smallk-Dominating Sets and Applications
• A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
• Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut
• A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees
• Filling Logarithmic Gaps in Distributed Complexity for Global Problems
• On the locality of bounded growth
• Round- and Message-Optimal Distributed Graph Algorithms
• Minor Excluded Network Families Admit Fast Distributed Algorithms
• Planar diameter via metric compression
• On the Relationship Between Clique-Width and Treewidth
• Low-Congestion Shortcuts without Embedding
• Distributed MST and Routing in Almost Mixing Time
• Distributed Computing
• Distributed verification and hardness of distributed approximation
• Distributed MST for constant diameter graphs

This page was built for publication: Low-congestion shortcut and graph parameters