Low-Congestion Shortcut and Graph Parameters

Hirotaka Kitagawa; Naoki Kitamura; Taisuke Izumi; Yota Otachi

REVIEW 3 major objections 5 minor 33 references

Low-Congestion Shortcut and Graph Parameters

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper establishes O(kD)-quality shortcuts in O(1) rounds for k-chordal graphs, closes the small-diameter MST gaps at D=3 and D=4, and shows bounded clique-width does not help.

desk verdict Strong k-chordal and D=3 shortcut results, but D=4 proof has a real gap and clique-width parameters are inconsistent; worth serious peer review. read the letter →

arxiv 1908.09473 v1 pith:HT7D62K7 submitted 2019-08-26 cs.DC

Naoki Kitamura , Hirotaka Kitagawa , Yota Otachi , Taisuke Izumi This is my paper · ORCID

classification cs.DC MSC 68W1505C85

keywords low-congestionshortcutsCONGESTmodelk-chordalgraphsclique-widthgraphdiameterminimumspanningtreepartwiseaggregationdistributedalgorithms

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper studies how three structural parameters of a network—chordality, diameter, and clique-width—control the round complexity of distributed computation in the CONGEST model, where each link carries $O(\log n)$ bits per round. It tries to establish three things: every $k$-chordal graph admits a low-congestion shortcut of quality $O(kD)$ built in $O(1)$ rounds, and this is nearly optimal; graphs of diameter $3$ and $4$ admit shortcuts of quality and construction time $\tilde{O}(n^{1/4})$ and $\tilde{O}(n^{1/3})$, respectively, which translate into minimum spanning tree (MST) algorithms at those speeds and close the known small-diameter MST gaps; and bounding clique-width by six does not help, because an $n$-vertex clique-width-$6$ graph still forces $\tilde{\Omega}(\sqrt{n}+D)$ rounds for MST. A shortcut is a set of extra edges added to each component to accelerate aggregation; its quality is the sum of the resulting component diameter (dilation) and the maximum edge congestion. If the paper is right, MST and related problems become provably fast on chordal-like and small-diameter networks, while clique-width is ruled out as a useful parameter for this purpose.

What carries the argument

The load-bearing object is the low-congestion shortcut: for each part $P_i$ of a partition, a set $H_i$ of extra edges such that $P_i + H_i$ has diameter at most $d$ and every edge of $G$ appears in at most $c$ of the augmented parts; the quality is $d+c$. The main construction scheme is one-hop extension: each node in a part adds each incident edge to its part's shortcut, which costs one round and already gives $O(kD)$ quality on $k$-chordal graphs through a chord argument on shortest paths. For diameter $3$ and $4$, random sampling is layered on top of one-hop extension: diameter $3$ samples incident edges with probability $n^{-1/2}$, while diameter $4$ uses an $(n^{1/3}\log^3 n)$-wise independent hash function $h$—a hash family in which any fixed collection of inputs behaves like independent uniform values—to sample edges with probability $1/h(u,i)$. The dilation analysis uses ruling sets and terminal sets inside each part to show that two far-apart nodes become connected by a short sampled path. The clique-width lower bound is carried by a recursively constructed graph that fits the same hard-instance framework used for general lower bounds.

What would settle it

Inspect the diameter-4 proof at Lemma 6: compute the probability that a fixed two-hop path $(a,b,c)$, with $a$ adjacent to one terminal set and $c$ adjacent to the other, is fully contained in $H_i$ under the stated sampling rule; if the correct value is $1/h(b,i)^2$ rather than $1/h(b,i)$, the union bound loses a factor and the claimed $\tilde{O}(n^{1/3})$ dilation needs a repaired argument.

Watch

Extended reading notes

Core claim

The central discovery is a tight connection between shortcut quality and three graph parameters. Theorem 3 shows that a one-round construction—each node contributes all its incident edges to its part's shortcut—produces a shortcut of quality $O(kD)$ for any $k$-chordal graph (a graph with no induced cycle longer than $k$), and Theorem 4 gives a matching lower bound up to polylogarithmic factors for $k\le D$ and $kD\le \sqrt{n}$. Theorem 5 gives two randomized constructions: for diameter $3$, quality and construction time $\tilde{O}(n^{1/4})$; for diameter $4$, quality and construction time $\tilde{O}(n^{1/3})$, matching the known lower bounds and immediately yielding MST algorithms at those speeds. Theorem 6 builds a clique-width-$6$ graph on which MST requires $\tilde{\Omega}(\sqrt{n}+D)$ rounds, so bounded clique-width does not make good shortcuts possible. The proofs identify one-hop extension plus selective random sampling of length-one or length-two paths as the mechanism that carries these upper bounds.

Load-bearing premise

The load-bearing premise is that the diameter-4 randomized sampling makes, for every far-apart pair of representative nodes, a two-hop path between their surrounding terminal sets appear in the shortcut with high probability; if that event fails, the $\tilde{O}(n^{1/3})$ result does not follow.

Editorial extensions

If this is right

In any $k$-chordal network with constant $k$, MST, approximate minimum cut, and approximate shortest paths become solvable in $\tilde{O}(D)$ rounds, matching the universal $\Omega(D)$ diameter lower bound up to polylogarithmic factors.
For diameter-$3$ networks, MST runs in $\tilde{O}(n^{1/4})$ rounds, and for diameter-$4$ networks in $\tilde{O}(n^{1/3})$ rounds, closing the small-diameter MST gaps.
The $k$-chordal construction is nearly optimal: for $k \le D$ and $kD \le \sqrt{n}$, no shortcut-based MST algorithm can do asymptotically better.
Bounded clique-width is not a viable route to fast MST: a clique-width-$6$ network can be as hard as the general $\tilde{\Omega}(\sqrt{n}+D)$ case.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

One consequence left implicit in the paper is that chordal graphs, the $k=3$ case, already receive a $\tilde{O}(D)$-round MST algorithm, placing them in the same fast category as planar and bounded-treewidth networks.
The ruling-set and terminal-set technique is a natural template for diameter $5$ and above, but the paper leaves that extension open; the obvious next step would be sampling paths of length $D-2$ to match the known lower-bound curve.
The clique-width result suggests that a graph parameter helps shortcuts only if it constrains diameter or chordality; construction complexity alone, such as clique-width, is orthogonal to the distributed bottleneck.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Things you should know: this paper has a genuinely nice O(1)-round shortcut for k-chordal graphs and a D=3 shortcut that matches the known lower bound. The D=4 half of Theorem 5 has a gap in the dilation proof, and the clique-width section has a parameter slip. I'd send it to a serious referee regardless.

What's actually new: the k-chordal result is the best thing here. The 1-hop extension scheme — every node in a part just adds all incident edges — gives quality O(kD) in one round. Lemma 1's induction is a clever use of chordality: it shows each consecutive pair of intersections between the graph shortest path and the part shortest path can be jumped in at most k steps. The lower bound construction is self-contained and plugs cleanly into the Das Sarma et al. framework. The D=3 construction is also well argued: terminal sets give many distinct second edges, and the sampling probability makes the failure event exponentially unlikely. The clique-width lower bound is structurally interesting as a six-label recursive construction, even if the writeup fumbles the parameters.

Where it goes soft: the D=4 dilation proof (Lemma 6) has a load-bearing error. A length-two path (a,b,c) enters the shortcut only if both edges (a,b) and (b,c) are added. The proof conditions on Y_b = h(b,i) and asserts Pr[X_b=1|Y_b=y] ≥ 1-(1-1/y)^{Δ(b)}. That inequality accounts only for b's random choices; the other endpoint's hash also matters. The per-path success probability is smaller and depends on h(a,i) and h(c,i), so the bound on X_b is unsupported. The independence step also uses n^{1/3} log^3 n-wise independence for all b in B without bounding |B|. So as written, the D=4 shortcut guarantee is not established. That is the main problem. The clique-width instance is stated as G(√n, log n/2), but Lemma 7's own proof requires 2p = Θ(√n) to get Ω~(√n); with p = log n/2 the bound is polylogarithmic. That is a fixable parameter inconsistency. Minor: the k-chordal lower bound takes K = k/2−1, so it silently assumes even k; that is cosmetic.

Bottom line: the k-chordal and D=3 results are solid and likely correct, the D=4 result is a genuine open question after this paper, and the clique-width result needs a parameter correction. The paper is worth a serious referee, with a clear request to repair or verify Lemma 6. If the authors fix it, the paper is strong; if they can't, the D=3 and k-chordal parts still justify publication.

Referee Report

3 major / 5 minor

Summary. The paper studies low-congestion shortcuts in the CONGEST model and their relation to three graph parameters. It claims (1) an O(1)-round algorithm constructing a shortcut of quality O(kD) for every k-chordal graph, together with a near-matching lower bound; (2) shortcut algorithms of quality and round complexity O~(n^{1/4}) for diameter-3 graphs and O~(n^{1/3}) for diameter-4 graphs, yielding MST algorithms that match known lower bounds; and (3) a negative result that clique-width six does not help, exhibited by an n-vertex graph on which MST requires Ω~(√n+D) rounds. The technical core is a 1-hop extension scheme for chordal graphs and two probabilistic edge-sampling constructions for small diameter.

Significance. If the results were fully established, the paper would close the MST complexity gap for diameters 3 and 4 and show that chordality is a parameter admitting optimal shortcuts; the clique-width lower bound would also rule out a natural candidate parameter. The paper is self-contained, uses the established Das Sarma et al. lower-bound framework, and the k-chordal upper bound is elegant and appears sound. The D=3 analysis is also coherent. The significance is high, but two load-bearing proofs, the D=4 dilation bound and the clique-width lower bound, are not valid as written.

major comments (3)

[Section 4.1, Lemma 6] The D=4 dilation proof does not match the stated edge-sampling algorithm. For a length-two path (a,b,c), the shortcut must contain both edges (a,b) and (b,c). In the algorithm, node b selects each incident edge independently with probability 1/h(b,i), so conditioning only on Y_b = h(b,i) gives Pr[X_b=1 | Y_b=y] >= 1 - (1 - 1/y^2)^{Δ(b)}, not the printed 1 - (1 - 1/y)^{Δ(b)}. With the weaker bound, the subsequent threshold event Y_b <= Δ(b)/log^2 n no longer yields the claimed failure probability e^{-Ω(log^2 n)}. Additionally, the proof asserts that Y_b for all b in B are independent because the hash is (n^{1/3} log^3 n)-wise independent; this requires |B| <= n^{1/3} log^3 n, and no such bound on the set of centers of the edge-disjoint path packing is given. Since Lemma 6 is the only support for the D=4 part of Theorem 5, the claimed O~(n^{1/3}) shortcut for diameter 4 is not established.
[Section 5, Lemma 7 and Theorem 6] The parameters in the clique-width lower bound do not produce the claimed Ω~(√n) bound. Lemma 7 places G(Γ,p) in G(O(Γ(2p+2)), Γ, 2p+2, 3p), so Theorem 2 gives a lower bound of Ω~(min{Γ/(3p), p}) up to constants. If the intended instance is G(√n, log n/2), then p = O(log n) and the bound is O(log n); if instead one takes 2p = Θ(√n) as the last sentence of the proof suggests, then Γ/(3p) = Θ(1). In neither case is Ω~(√n+D) obtained, and the stated n-vertex instance is not matched to the claim. Consequently Theorem 6 is unsupported as written.
[Section 3.3, Theorem 4 and Lemma 2] The lower-bound construction uses K = k/2 - 1, which is an integer only for even k, yet Theorem 4 is stated for all k with k <= D and kD <= √n. The definition of G(k,x,N) and the chordality proof in Lemma 2 depend on K being integral; for odd k the construction is not well-defined. The upper bound in Theorem 3 is unaffected, but the claimed near-optimal lower bound for all k needs either an explicit even-k restriction or a separate treatment of odd k.

minor comments (5)

[Section 5 heading] The heading contains a typo: 'Low-Congstion' should be 'Low-Congestion'.
[Section 5, Lemma 7] The formal vertex set T = {u_i^j | 0 <= i <= 2p-1, 0 <= j <= p} is inconsistent with the binary-tree structure and with the recursive definition G(Γ,p) = G(Γ,p-1) ⊕ G(Γ,p-1); the index range should presumably be 0 <= i <= 2^j - 1. This also affects the vertex count and the relation between p and n.
[Section 4.1, Lemma 6] The last displayed inequality in the lemma reads Pr[X=1] >= Pr[X=1 ∧ Y=1] Pr[Y=1]; it should be Pr[X=1] >= Pr[X=1 ∧ Y=1] = Pr[X=1 | Y=1] Pr[Y=1].
[Section 4.2, Preprocessing] The preprocessing identifies parts of diameter Θ(κ_D) arbitrarily, whereas the analysis assumes large parts have diameter larger than 12κ_D log^3 n. The logarithmic slack between these thresholds should be stated explicitly so that the congestion and dilation bounds remain valid.
[Section 3.3, Lemma 3] The definition of X_i uses cases 'i mod K = 2' and 'i mod K ≠ 2'; when K = 1 the partition becomes degenerate. The range of k for which the construction is non-degenerate should be clarified.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the shortcut constructions are self-contained and checked against external lower-bound frameworks.

full rationale

The paper's central contributions are constructive upper bounds (Theorems 3 and 5) and a lower bound (Theorem 6), none of which reduces to its own inputs. The k-chordal shortcut construction is the 1-hop extension scheme: every node adds all incident edges, and Lemma 1 proves the dilation bound O(kD) directly from the definition of k-chordality. No parameter is fitted to data, and no output quantity is defined in terms of the claimed result. The small-diameter algorithms combine the 1-hop extension with randomized edge sampling; the congestion and dilation analyses are self-contained probabilistic arguments based on ruling sets, terminal sets, and hash functions. Although the D=4 dilation proof in Lemma 6 contains a cited probabilistic concern (it conditions only on the center's hash value while requiring both edges of a length-two path to be sampled), that is a potential correctness gap, not circularity: the claimed shortcut quality is not assumed, fitted, or defined into existence. The lower bounds for k-chordal graphs and clique-width-six graphs are obtained by embedding the constructed instances into the externally established Das Sarma et al. framework (Theorem 2), and the MST consequences use the external meta-theorem of Ghaffari-Haeupler and Haeupler-Li (Theorem 1). The authors cite prior work by one of the authors (Haeupler, Izumi, and Zuzic), but those citations are used as background or as existing shortcut results for other graph classes, not as the load-bearing justification for the new theorems. No self-citation supplies a uniqueness theorem, no ansatz is smuggled in by citation, and no known result is merely renamed. The derivation chain is therefore not circular, despite any correctness questions in Lemma 6.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters are fitted to data; the bounds are proven for arbitrary graphs in the stated classes. The paper relies on known external shortcut meta-theorems and lower-bound frameworks, not on self-citations. Constants such as 12, 14, and 6 in Section 4 are proof-internal choices that do not affect asymptotics.

assumptions (4)

domain assumption Theorem 1 of Ghaffari-Haeupler and Haeupler-Li: a shortcut of quality q constructible in f rounds yields O~(f+q)-round MST, min-cut, and SSSP algorithms.
Invoked in Section 1.2 to translate shortcut constructions into MST algorithms; stated without proof from the cited papers.
domain assumption Theorem 2 of Das Sarma et al.: on graph class G(n,b,l,c), every MST algorithm requires Omega~(min{b/c, l/2-1}) rounds.
Used in Sections 3.3 and 5 to derive lower bounds after proving membership of constructed graphs in G(...).
standard math Existence of an (alpha, alpha+1)-ruling set in every graph.
Used in Section 4.1 to select ruling sets for the dilation analysis.
standard math Wegman-Carter k-wise independent hash families with small seeds exist.
Used in Section 4.2 so all nodes can construct the shared hash function h from a broadcast seed.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Low-Congestion Shortcut and Graph Parameters." pith.science (2026). https://pith.science/paper/HT7D62K7

@misc{pith2026190809473,
  author       = {Pith},
  title        = {Pith review of: Low-Congestion Shortcut and Graph Parameters},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HT7D62K7}},
  note         = {Machine review of arXiv:1908.09473}
}

abstract

The concept of low-congestion shortcuts is initiated by Ghaffari and Haeupler [SODA2016] for addressing the design of CONGEST algorithms running fast in restricted network topologies. Specifically, given a specific graph class $X$, an $f$-round algorithm of constructing shortcuts of quality $q$ for any instance in $X$ results in $\tilde{O}(q + f)$-round algorithms of solving several fundamental graph problems such as minimum spanning tree and minimum cut, for $X$. In this paper, we consider the relationship between the quality of low-congestion shortcuts and three major graph parameters, chordality, diameter, and clique-width. The main contribution of the paper is threefold: (1) We show an $O(1)$-round algorithm which constructs a low-congestion shortcut with quality $O(kD)$ for any $k$-chordal graph, and prove that the quality and running time of this construction is nearly optimal up to polylogarithmic factors. (2) We present two algorithms, each of which constructs a low-congestion shortcut with quality $\tilde{O}(n^{1/4})$ in $\tilde{O}(n^{1/4})$ rounds for graphs of $D=3$, and that with quality $\tilde{O}(n^{1/3})$ in $\tilde{O}(n^{1/3})$ rounds for graphs of $D=4$ respectively. These results obviously deduce two MST algorithms running in $\tilde{O}(n^{1/4})$ and $\tilde{O}(n^{1/3})$ rounds for $D=3$ and $4$ respectively, which almost close the long-standing complexity gap of the MST construction in small-diameter graphs originally posed by Lotker et al. [Distributed Computing 2006]. (3) We show that bounding clique-width does not help the construction of good shortcuts by presenting a network topology of clique-width six where the construction of MST is as expensive as the general case.

Figures

Figures reproduced from arXiv: 1908.09473 by the authors.

**Figure 1.** Example of G(O(lb), b, l, O(log n)) Definition 3. For n, b, c ≥ 0 and l ≥ 3, the graph class G(n, b, l, c) is defined as the set of n-vertex graph G = (V, E) satisfying the following conditions: • (C1) The vertex set V is partitioned into ` disjoint vertex sets X = {X1, X2, . . ., X` } such that X1 and X` are singletons (let X1 = {s} and X` = {r}). • (C2) The vertex set V\{s,r} is partitioned into b disjoint connect… view at source ↗

**Figure 2.** Proof of Lemma 1. is clique 𝑥 𝐾 = 𝑘 2 − 1 1 ・・・ 𝑁 𝑣1,0 𝑣1,1 𝑣1,𝑥 𝑣2,𝑥𝐾 𝑣3,𝑥𝐾 𝑣𝑁,𝑥𝐾 𝑣2,0 𝑣3,0 𝑣𝑁,0 𝑣2,𝐾 𝑣3,𝐾 𝑣𝑁,𝐾 ・・・・・・・・・・・・・・・・・・・・・・・・ [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

**Figure 3.** Example of k-chordal graph G(k, x, N). argument. The parameters x and N are adjusted later for obtaining the claimed lower bound. Let K = k/2−1 for short. The vertex set and edge set of G(k, x, N) is defined as follows: • V(k, x, N) = {v1,j | 0 ≤ j ≤ x} ∪ {vi,j |2 ≤ i ≤ N, 0 ≤ j ≤ xK}. • E(k, x, N) = E1 ∪ E2 ∪ E3 ∪ E4 such that E1 = {{v1,j , v1,j+1} | 0 ≤ j ≤ x − 1}, E2 = {{vi,j , vi,j+1} | 2 ≤ i ≤ N, 0 ≤ j ≤ xK − 1… view at source ↗

Figures from the paper (3 more)

**Figure 4.** Figure 4: Proof of Lemma 2. We consider a cycle X in G(k, x, N). Let l and r be the minimum/maximum indices of the rows X intersects, Similarly, let t and b be the minimum/maximum indices of the columns X intersects. Let m be the index such that |Cm ∩ X| maximizes, and let am = …

**Figure 5.** Figure 5: Graph G ⊕ H. Now we are ready to define G(Γ, p). The construction is recursive. First, we define G(Γ, 1) as follows: (1) Prepare a (2Γ)-biclique KΓ,Γ where one side has label 2, and the other side has label 3. Note that two labels suffice to construct KΓ,Γ. (2) Add thr…

**Figure 6.** Figure 6: Example of clique-width 6 graph G(Γ, p). Acknowledgements This work was supported by JSPS KAKENHI Grant Numbers JP18H04091, JP18K11168, JP18K11169, JP19K11824, and JP19J22696, and JST SICORP Grant Number JPMJSC1606, Japan. References [1] Amir Abboud, Keren Censor-Hille…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

33 extracted references · 20 canonical work pages

[1]

AmirAbboud,KerenCensor-Hillel,andSeriKhoury. Near-linearlowerboundsfordistributeddistance computations,eveninsparsenetworks.In Proceedingsof30ndInternationalSymposiumonDistributed Computing (DISC), pages 29–42, 2016.doi:10.1007/978-3-662-53426-7_3

work page doi:10.1007/978-3-662-53426-7_3 2016
[2]

Networkdecomposition and locality in distributed computation

BaruchAwerbuch,AndrewV.Goldberg,MichaelLuby,andSergeA.Plotkin. Networkdecomposition and locality in distributed computation. InProceedings of 30th Annual Symposium on Foundations of Computer Science (FOCS), pages 364–369, 1989.doi:10.1109/SFCS.1989.63504

arXiv 1989
[3]

Corneil and Udi Rotics

Derek G. Corneil and Udi Rotics. On the relationship between clique-width and treewidth.SIAM Journal on Computing, pages 825–847, 2005.doi:10.1137/S0097539701385351

work page doi:10.1137/s0097539701385351 2005
[4]

Upper bounds to the clique width of graphs.Discrete Applied Mathematics, pages 77–114, 2000.doi:10.1016/S0166-218X(99)00184-5

Bruno Courcelle and Stephan Olariu. Upper bounds to the clique width of graphs.Discrete Applied Mathematics, pages 77–114, 2000.doi:10.1016/S0166-218X(99)00184-5

doi:10.1016/s0166-218x(99)00184-5
[5]

Distributed approximation: a survey

Michael Elkin. Distributed approximation: a survey. ACM SIGACT News, pages 40–57, 2004. doi:10.1145/1054916.1054931

work page arXiv 2004
[6]

An unconditional lower bound on the time-approximation trade-oﬀ for the distributed minimumspanningtreeproblem

Michael Elkin. An unconditional lower bound on the time-approximation trade-oﬀ for the distributed minimumspanningtreeproblem. SIAMJournalonComputing ,pages433–456,2006. doi:10.1137/ S0097539704441058

work page 2006
[7]

Gallager, Pierre A

Robert G. Gallager, Pierre A. Humblet, and Philip M. Spira. A distributed algorithm for minimum- weight spanning trees.ACM Transactions on Programming Languages and Systems (TOPLAS), pages 66–77, 1983.doi:10.1145/357195.357200. 17

arXiv 1983
[8]

Garay, Shay Kutten, and David Peleg

Juan A. Garay, Shay Kutten, and David Peleg. A sublinear time distributed algorithm for minimum- weight spanning trees. SIAM Journal on Computing, pages 302–316, 1998. doi:10.1137/ S0097539794261118

work page 1998

Show all 33 references

[9]

The intersection graphs of subtrees in trees are exactly the chordal graphs.Journal of Combinatorial Theory, Series B, pages 47–56, 1974.doi:10.1016/0095-8956(74)90094-X

Fˇanicˇa Gavril. The intersection graphs of subtrees in trees are exactly the chordal graphs.Journal of Combinatorial Theory, Series B, pages 47–56, 1974.doi:10.1016/0095-8956(74)90094-X

1974 doi
[10]

Near-optimal scheduling of distributed algorithms

Mohsen Ghaﬀari. Near-optimal scheduling of distributed algorithms. InProceedings of the 2015 ACMSymposiumonPrinciplesofDistributedComputing(PODC) ,pages3–12,2015. doi:10.1145/ 2767386.2767417

2015
[11]

DistributedalgorithmsforplanarnetworksII:low-congestion shortcuts, mst, and min-cut

MohsenGhaﬀariandBernhardHaeupler. DistributedalgorithmsforplanarnetworksII:low-congestion shortcuts, mst, and min-cut. InProceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms (SODA), pages 202–219, 2016.doi:10.1137/1.9781611974331.ch16

2016 doi
[12]

Distributed MST and broadcast with fewer messages, and faster gossiping

Mohsen Ghaﬀari and Fabian Kuhn. Distributed MST and broadcast with fewer messages, and faster gossiping. InProceedings of 32nd International Symposium on Distributed Computing (DISC), pages 30:1–30:12, 2018.doi:10.4230/LIPIcs.DISC.2018.30

2018 doi
[13]

DistributedMSTandroutinginalmostmixingtime

MohsenGhaﬀari,FabianKuhn,andHsin-HaoSu. DistributedMSTandroutinginalmostmixingtime. In Proceedings of 31nd International Symposium on Distributed Computing (DISC), pages 131–140,
[14]

New distributed algorithms in almost mixing time via transformations from parallel algorithms

Mohsen Ghaﬀari and Jason Li. New distributed algorithms in almost mixing time via transformations from parallel algorithms. InProceedings of 32nd International Symposium on Distributed Computing (DISC), pages 31:1–31:16, 2018.doi:10.4230/LIPIcs.DISC.2018.31

2018 doi
[15]

Time-messagetrade-oﬀsindistributedalgorithms

RobertGmyrandGopalPandurangan. Time-messagetrade-oﬀsindistributedalgorithms. In Proceed- ings of 32nd International Symposium on Distributed Computing (DISC), pages 32:1–32:18, 2018. doi:10.4230/LIPIcs.DISC.2018.32

2018 doi
[17]

Low-congestion shortcuts without embedding

Bernhard Haeupler, Taisuke Izumi, and Goran Zuzic. Low-congestion shortcuts without embedding. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC), pages 451–460, 2016.doi:10.1145/2933057.2933112

2016
[18]

Bernhard Haeupler, Taisuke Izumi, and Goran Zuzic. Near-optimal low-congestion shortcuts on boundedparametergraphs.In Proceedingsof30ndInternationalSymposiumonDistributedComputing (DISC), pages 158–172, 2016.doi:10.1007/978-3-662-53426-7_12

2016 doi
[19]

Faster distributed shortest path approximations via shortcuts

Bernhard Haeupler and Jason Li. Faster distributed shortest path approximations via shortcuts. In Proceedings of 32nd International Symposium on Distributed Computing (DISC), pages 33:1–33:14,
[20]

Minorexcludednetworkfamiliesadmitfastdistributed algorithms

BernhardHaeupler,JasonLi,andGoranZuzic. Minorexcludednetworkfamiliesadmitfastdistributed algorithms. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC), pages 465–474, 2018.doi:10.1145/3212734.3212776. 18

2018
[21]

MSTin O(1)roundsofcongestedclique

TomaszJurdzinskiandKrzysztofNowicki. MSTin O(1)roundsofcongestedclique. In Proceedingsof the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2620–2632,
[22]

Fastdistributedconstructionofsmall k-dominatingsetsandapplications

ShayKuttenandDavidPeleg. Fastdistributedconstructionofsmall k-dominatingsetsandapplications. Journal of Algorithms, pages 40–66, 1998.doi:10.1006/jagm.1998.0929

1998
[23]

Distributed treewidth computation.arXiv, 2018

Jason Li. Distributed treewidth computation.arXiv, 2018. arXiv:1805.10708

2018 arXiv
[24]

doi:10.1137/1.9781611975031.167

doi
[25]

Filling logarithmic gaps in distributed complexity for global problems

Hiroaki Ookawa and Taisuke Izumi. Filling logarithmic gaps in distributed complexity for global problems. InProccedings of 41st International Conference on Current Trends in Theory and Practice of Informatics (SOFSEM), pages 377–388, 2015.doi:10.1007/978-3-662-46078-8_31

2015 doi
[26]

Intersection graphs: An introduction.arXiv, 2014

Madhumangal Pal. Intersection graphs: An introduction.arXiv, 2014. arXiv:1404.5468

2014 arXiv
[27]

Distributed MST for constant diameter graphs

Zvi Lotker, Boaz Patt-Shamir, and David Peleg. Distributed MST for constant diameter graphs. Distributed Computing, pages 453–460, 2006.doi:10.1007/s00446-005-0127-6

2006 doi
[28]

The distributed minimum spanning tree problem.Bulletin of the European Association for Theoretical Computer Science (EATCS), 2018

Gopal Pandurangan, Peter Robinson, and Michele Scquizzato. The distributed minimum spanning tree problem.Bulletin of the European Association for Theoretical Computer Science (EATCS), 2018. URL: http://eatcs.org/beatcs/index.php/beatcs/article/view/538

2018
[29]

A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction.SIAM Journal on Computing, pages 1427–1442, 2000

David Peleg and Vitaly Rubinovich. A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction.SIAM Journal on Computing, pages 1427–1442, 2000. doi:10.1137/S0097539700369740

doi
[30]

Atime-andmessage-optimaldistributed algorithm for minimum spanning trees

GopalPandurangan,PeterRobinson,andMicheleScquizzato. Atime-andmessage-optimaldistributed algorithm for minimum spanning trees. InProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 743–756, 2017.doi:10.1145/3055399.3055449

2017
[31]

Newhashfunctionsandtheiruseinauthenticationandsetequality

MarkN.WegmanandLarryCarter. Newhashfunctionsandtheiruseinauthenticationandsetequality. Journal of Computer and System Sciences, pages 265–279, 1981.doi:10.1016/0022-0000(81) 90033-7. 19

1981 doi
[33]

In Proceedings of the 43th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 363–372, 2011.doi:10.1145/1993636.1993686

AtishDasSarma,StephanHolzer,LiahKor,AmosKorman,DanuponNanongkai,GopalPandurangan, DavidPeleg,andRogerWattenhofer.Distributedveriﬁcationandhardnessofdistributedapproximation. In Proceedings of the 43th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 363–372, 20...

2011
[2017]

doi:10.1145/3087801.3087827
[2018]

doi:10.4230/LIPIcs.DISC.2018.33

2018 doi

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

AmirAbboud,KerenCensor-Hillel,andSeriKhoury. Near-linearlowerboundsfordistributeddistance computations,eveninsparsenetworks.In Proceedingsof30ndInternationalSymposiumonDistributed Computing (DISC), pages 29–42, 2016.doi:10.1007/978-3-662-53426-7_3

work page doi:10.1007/978-3-662-53426-7_3 2016

[2] [2]

Networkdecomposition and locality in distributed computation

BaruchAwerbuch,AndrewV.Goldberg,MichaelLuby,andSergeA.Plotkin. Networkdecomposition and locality in distributed computation. InProceedings of 30th Annual Symposium on Foundations of Computer Science (FOCS), pages 364–369, 1989.doi:10.1109/SFCS.1989.63504

arXiv 1989

[3] [3]

Corneil and Udi Rotics

Derek G. Corneil and Udi Rotics. On the relationship between clique-width and treewidth.SIAM Journal on Computing, pages 825–847, 2005.doi:10.1137/S0097539701385351

work page doi:10.1137/s0097539701385351 2005

[4] [4]

Upper bounds to the clique width of graphs.Discrete Applied Mathematics, pages 77–114, 2000.doi:10.1016/S0166-218X(99)00184-5

Bruno Courcelle and Stephan Olariu. Upper bounds to the clique width of graphs.Discrete Applied Mathematics, pages 77–114, 2000.doi:10.1016/S0166-218X(99)00184-5

doi:10.1016/s0166-218x(99)00184-5

[5] [5]

Distributed approximation: a survey

Michael Elkin. Distributed approximation: a survey. ACM SIGACT News, pages 40–57, 2004. doi:10.1145/1054916.1054931

work page arXiv 2004

[6] [6]

An unconditional lower bound on the time-approximation trade-oﬀ for the distributed minimumspanningtreeproblem

Michael Elkin. An unconditional lower bound on the time-approximation trade-oﬀ for the distributed minimumspanningtreeproblem. SIAMJournalonComputing ,pages433–456,2006. doi:10.1137/ S0097539704441058

work page 2006

[7] [7]

Gallager, Pierre A

Robert G. Gallager, Pierre A. Humblet, and Philip M. Spira. A distributed algorithm for minimum- weight spanning trees.ACM Transactions on Programming Languages and Systems (TOPLAS), pages 66–77, 1983.doi:10.1145/357195.357200. 17

arXiv 1983

[8] [8]

Garay, Shay Kutten, and David Peleg

Juan A. Garay, Shay Kutten, and David Peleg. A sublinear time distributed algorithm for minimum- weight spanning trees. SIAM Journal on Computing, pages 302–316, 1998. doi:10.1137/ S0097539794261118

work page 1998