Paper Citation Record · LEDGER

Deterministic Almost-Linear-Time Gomory-Hu Trees

As of 20 August 2026, this Paper Citation Record lists 45 of 45 outbound references and 1 inbound Pith citation observation for arXiv:2507.20354.

A citation records a reference. It does not transfer a finding from one paper to another.

pith.paper-citation-record.v1
2507.20354 v1

Coverage vector

measured 45 of 45 reference resolution

Typed states for the displayed outbound observations.

Source: paper_references, paper_reference_links, observed 2026-08-15T17:57:01.037448Z

measured 46 of 46 standing notices

One-hop event checks from named stored sources.

Source: scholarly_work_events, retraction_status_cache, observed 2026-08-20T06:33:59.587034+00:00

measured 1 of 1 inbound itemization

Pith citing papers itemized under the disclosed page cap.

Source: paper_references, paper_reference_links, observed 2026-08-01T03:55:26.716428Z

measured 0 of 1 external citation measurements

A source-named dated measurement, never combined with another source.

Source: cited_works

Reference resolution

45 of 45 outbound references displayed

verified exact1
verified fuzzy23
unresolved21
parse uncertain0
malformed identifier0
metadata mismatch0

External citation measurements

No source-named external measurement is stored.

Outbound references

Observation 04617df2-734a-42f6-a4c4-12fe3011a590 · outbound

This paper cites Directly compute λ(s,t ) for t∈V (T ) when|V (T )|< 100.

Deterministic Almost-Linear-Time Gomory-Hu Trees Directly compute λ(s,t ) for t∈V (T ) when|V (T )|< 100

Reference 1

Resolution: verified fuzzy; raw_fallback, observed 2026-08-15T17:57:01.603790Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation 03271bc8-36c5-43c1-8b2d-f86bc719a8e2 · outbound

This paper cites Ifs̸= c, Update(c,λ (s,c )) by running the deterministic (s,c )-maxflow algorithm from [vdBCP+23].

Deterministic Almost-Linear-Time Gomory-Hu Trees Ifs̸= c, Update(c,λ (s,c )) by running the deterministic (s,c )-maxflow algorithm from [vdBCP+23]

Reference 2

Resolution: verified fuzzy; raw_fallback, observed 2026-08-15T17:57:01.593244Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation 2a83e8a7-c7f8-488a-8f55-5d470e3ca21d · outbound

This paper cites For each i >0, contract V\Wi to one vertex (labeled as s) and denote G, T after contraction by Gi, T (1) i , then call (Gi,T (1) i ,s,k ).

Deterministic Almost-Linear-Time Gomory-Hu Trees For each i >0, contract V\Wi to one vertex (labeled as s) and denote G, T after contraction by Gi, T (1) i , then call (Gi,T (1) i ,s,k )

Reference 3

Resolution: verified fuzzy; raw_fallback, observed 2026-08-15T17:57:01.581344Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation 53875271-69ac-4fbb-ab54-dc7aac31c3eb · outbound

This paper cites For each A∈F , we delete subtrees in A from T and obtain a new tree.

Deterministic Almost-Linear-Time Gomory-Hu Trees For each A∈F , we delete subtrees in A from T and obtain a new tree

Reference 4

Resolution: verified fuzzy; raw_fallback, observed 2026-08-15T17:57:01.569080Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation b680e530-8aa9-4767-aef6-9850859b7f1b · outbound

This paper cites Let T (3) be the tree obtained by removing V (T0)\{s} from T and adding the edge (s,c ).

Deterministic Almost-Linear-Time Gomory-Hu Trees Let T (3) be the tree obtained by removing V (T0)\{s} from T and adding the edge (s,c )

Reference 5

Resolution: verified fuzzy; raw_fallback, observed 2026-08-15T17:57:01.558543Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation 0246b267-9e88-4452-b15e-cf653756b6e3 · outbound

This paper cites an unresolved cited work.

Deterministic Almost-Linear-Time Gomory-Hu Trees Unresolved cited work

Reference 6

Resolution: unresolved; raw_fallback, observed 2026-08-15T17:57:01.547921Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation 47e6acce-0d9f-4390-8a65-09f2b0d57d73 · outbound

This paper cites an unresolved cited work.

Deterministic Almost-Linear-Time Gomory-Hu Trees Unresolved cited work

Reference 7

Resolution: unresolved; raw_fallback, observed 2026-08-15T17:57:01.537704Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation 78ab397d-235c-4351-967d-bc4e59843251 · outbound

This paper cites an unresolved cited work.

Deterministic Almost-Linear-Time Gomory-Hu Trees Unresolved cited work

Reference 8

Resolution: unresolved; raw_fallback, observed 2026-08-15T17:57:01.527750Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation fa32417f-d266-4737-8353-2e7bc2c63994 · outbound

This paper cites the number of clusters in X that do not form a cut of value less than τ is bounded by γexpDecomp·ψ·|U|.

Deterministic Almost-Linear-Time Gomory-Hu Trees the number of clusters in X that do not form a cut of value less than τ is bounded by γexpDecomp·ψ·|U|

Reference 9

Resolution: verified fuzzy; raw_fallback, observed 2026-08-15T17:57:01.516329Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation e2dd984f-c05e-418f-9ac9-39fc21aab757 · outbound

This paper cites U as CrossingU(X,Y ) = min{|(X∩Y )∩ U|,|(X∩U)\Y|}.

Deterministic Almost-Linear-Time Gomory-Hu Trees U as CrossingU(X,Y ) = min{|(X∩Y )∩ U|,|(X∩U)\Y|}

Reference 10

Resolution: verified fuzzy; raw_fallback, observed 2026-08-15T17:57:01.505875Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation 7d9466a9-982e-4f22-953c-3fe1b33ba58d · outbound

This paper cites an unresolved cited work.

Deterministic Almost-Linear-Time Gomory-Hu Trees Unresolved cited work

Reference 11

Resolution: unresolved; raw_fallback, observed 2026-08-15T17:57:01.494765Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation 45d9690b-e6d0-4416-85ce-0d02f78a58de · outbound

This paper cites Since the total amount of sink capacity is at most ψ·τ·γexpDecomp·|U|, we have by the existence of a feasible flow that 2·w(Ecrossing)≤ψ·τ·γexpDecomp·|U|.

Deterministic Almost-Linear-Time Gomory-Hu Trees Since the total amount of sink capacity is at most ψ·τ·γexpDecomp·|U|, we have by the existence of a feasible flow that 2·w(Ecrossing)≤ψ·τ·γexpDecomp·|U|

Reference 12

Resolution: verified fuzzy; raw_fallback, observed 2026-08-15T17:57:01.484590Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation 57d648bc-9567-46e8-b416-43193e5b68b0 · outbound

This paper cites Let ℓ be the number of sets X∈X with w(∂X)≥τ.

Deterministic Almost-Linear-Time Gomory-Hu Trees Let ℓ be the number of sets X∈X with w(∂X)≥τ

Reference 13

Resolution: verified fuzzy; raw_fallback, observed 2026-08-15T17:57:01.474020Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation 1796cbfb-6ef2-4f48-b56f-a905b967bd12 · outbound

This paper cites For X∈X , we further have that G[X] is a (ψ·τ)- expander w.r.t.

Deterministic Almost-Linear-Time Gomory-Hu Trees For X∈X , we further have that G[X] is a (ψ·τ)- expander w.r.t

Reference 14

Resolution: verified fuzzy; raw_fallback, observed 2026-08-15T17:57:01.464023Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation 694650c7-c4cd-42c9-94ff-76df5a403b04 · outbound

This paper cites clusters where X∩Y∩U and (X∩U)\Y are both non-empty, is upper bounded by CrossingU(X,Y ).

Deterministic Almost-Linear-Time Gomory-Hu Trees clusters where X∩Y∩U and (X∩U)\Y are both non-empty, is upper bounded by CrossingU(X,Y )

Reference 15

Resolution: verified fuzzy; raw_fallback, observed 2026-08-15T17:57:01.453566Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation f2de972a-5a51-40d9-98bc-5c49b13d3ade · outbound

This paper cites Further, every edge on P is of weight at least τ.

Deterministic Almost-Linear-Time Gomory-Hu Trees Further, every edge on P is of weight at least τ

Reference 16

Resolution: verified fuzzy; raw_fallback, observed 2026-08-15T17:57:01.442762Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation ebd810d8-96a0-43a7-adfc-4f1d619314e7 · outbound

This paper cites Further, e is of weight less than τ.

Deterministic Almost-Linear-Time Gomory-Hu Trees Further, e is of weight less than τ

Reference 17

Resolution: verified fuzzy; raw_fallback, observed 2026-08-15T17:57:01.431622Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation 7f02ea5f-1c84-4410-b8e4-2527d0119703 · outbound

This paper cites an unresolved cited work.

Deterministic Almost-Linear-Time Gomory-Hu Trees Unresolved cited work

Reference 18

Resolution: unresolved; raw_fallback, observed 2026-08-15T17:57:01.420915Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation 76cda3b5-39a3-4d9a-89bd-6dc0e6c9f2e1 · outbound

This paper cites an unresolved cited work.

Deterministic Almost-Linear-Time Gomory-Hu Trees Unresolved cited work

Reference 19

Resolution: unresolved; raw_fallback, observed 2026-08-15T17:57:01.410269Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation c65f25ae-e183-4519-999e-814f790ffdd9 · outbound

This paper cites an unresolved cited work.

Deterministic Almost-Linear-Time Gomory-Hu Trees Unresolved cited work

Reference 20

Resolution: unresolved; raw_fallback, observed 2026-08-15T17:57:01.400250Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation 7d2d2bdb-5b9b-454c-844c-167d977a14a2 · outbound

This paper cites an unresolved cited work.

Deterministic Almost-Linear-Time Gomory-Hu Trees Unresolved cited work

Reference 21

Resolution: unresolved; raw_fallback, observed 2026-08-15T17:57:01.389614Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation d572ea9f-ebe7-4a57-8ada-952f85d2e868 · outbound

This paper cites an unresolved cited work.

Deterministic Almost-Linear-Time Gomory-Hu Trees Unresolved cited work

Reference 22

Resolution: unresolved; raw_fallback, observed 2026-08-15T17:57:01.378536Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation e07ef131-d120-41c5-bc7c-be4caf80345a · outbound

This paper cites an unresolved cited work.

Deterministic Almost-Linear-Time Gomory-Hu Trees Unresolved cited work

Reference 23

Resolution: unresolved; raw_fallback, observed 2026-08-15T17:57:01.368805Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation 5fc886e8-26ca-4353-baf8-387de7946bd8 · outbound

This paper cites Such a vertex must exist as otherwise the path is only supported on vertices in CG,U,τ(r) and does not cross the cut ∂TG,U,rCG,U,τ(r).

Deterministic Almost-Linear-Time Gomory-Hu Trees Such a vertex must exist as otherwise the path is only supported on vertices in CG,U,τ(r) and does not cross the cut ∂TG,U,rCG,U,τ(r)

Reference 24

Resolution: verified fuzzy; raw_fallback, observed 2026-08-15T17:57:01.358281Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation 353f3094-3809-400d-a545-0c61dccd3d9c · outbound

This paper cites By the above item, the segmentP [y,r ] does not contain a vertex outside CG,U,τ(r).

Deterministic Almost-Linear-Time Gomory-Hu Trees By the above item, the segmentP [y,r ] does not contain a vertex outside CG,U,τ(r)

Reference 25

Resolution: verified fuzzy; raw_fallback, observed 2026-08-15T17:57:01.347531Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation 05dda059-ce5a-429a-9e15-e2d74eaf5658 · outbound

This paper cites an unresolved cited work.

Deterministic Almost-Linear-Time Gomory-Hu Trees Unresolved cited work

Reference 26

Resolution: unresolved; raw_fallback, observed 2026-08-15T17:57:01.337034Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation 1407c844-a427-4f1e-8dc6-a9417ed6b67b · outbound

This paper cites This implies the claim immediately.

Deterministic Almost-Linear-Time Gomory-Hu Trees This implies the claim immediately

Reference 27

Resolution: verified fuzzy; raw_fallback, observed 2026-08-15T17:57:01.326347Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation d97f685d-39c6-4f9d-b96c-cf207328e6d3 · outbound

This paper cites an unresolved cited work.

Deterministic Almost-Linear-Time Gomory-Hu Trees Unresolved cited work

Reference 28

Resolution: unresolved; raw_fallback, observed 2026-08-15T17:57:01.316088Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation caaa4e93-3f80-450c-8a6f-1b2ac23b0bb2 · outbound

This paper cites Thus, when cG,U,r(x) is a descen- dent of cG,U,r(w), we have MG,x,r⊆MG,w,r, and vice versa.

Deterministic Almost-Linear-Time Gomory-Hu Trees Thus, when cG,U,r(x) is a descen- dent of cG,U,r(w), we have MG,x,r⊆MG,w,r, and vice versa

Reference 29

Resolution: verified fuzzy; raw_fallback, observed 2026-08-15T17:57:01.305723Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation 4382fedf-4148-4840-bf7a-71845618384c · outbound

This paper cites Note that for each u ∈ A with associated endpoint v inCG,U,τ(r) contributes wTG,U,r(u,v ) to the cut value wTG,U,r(∂TG,U,rCG,U,τ(r)).

Deterministic Almost-Linear-Time Gomory-Hu Trees Note that for each u ∈ A with associated endpoint v inCG,U,τ(r) contributes wTG,U,r(u,v ) to the cut value wTG,U,r(∂TG,U,rCG,U,τ(r))

Reference 30

Resolution: verified fuzzy; raw_fallback, observed 2026-08-15T17:57:01.294413Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation 8b36d11e-8493-465d-ae99-c7a9ca8eebbb · outbound

This paper cites sampling threshold.

Deterministic Almost-Linear-Time Gomory-Hu Trees sampling threshold

Reference 31

Resolution: verified fuzzy; raw_fallback, observed 2026-08-15T17:57:01.283777Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation adf0bbf8-e9f7-4762-9354-12d0ad266609 · outbound

This paper cites an unresolved cited work.

Deterministic Almost-Linear-Time Gomory-Hu Trees Unresolved cited work

Reference 32

Resolution: unresolved; raw_fallback, observed 2026-08-15T17:57:01.272882Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation 754e5377-fac6-4065-80ee-484ce573a2b8 · outbound

This paper cites an unresolved cited work.

Deterministic Almost-Linear-Time Gomory-Hu Trees Unresolved cited work

Reference 33

Resolution: unresolved; raw_fallback, observed 2026-08-15T17:57:01.261970Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation e04d8a3b-997c-4e07-9be2-7f4287f1fe3b · outbound

This paper cites an unresolved cited work.

Deterministic Almost-Linear-Time Gomory-Hu Trees Unresolved cited work

Reference 34

Resolution: unresolved; raw_fallback, observed 2026-08-15T17:57:01.251869Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation e4d6b667-dcc7-4d68-a1ad-9fbbf04f6e9a · outbound

This paper cites an unresolved cited work.

Deterministic Almost-Linear-Time Gomory-Hu Trees Unresolved cited work

Reference 35

Resolution: unresolved; raw_fallback, observed 2026-08-15T17:57:01.241168Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation ed421e60-19f0-4510-b5bd-cfe74f6e9db1 · outbound

This paper cites an unresolved cited work.

Deterministic Almost-Linear-Time Gomory-Hu Trees Unresolved cited work

Reference 36

Resolution: unresolved; raw_fallback, observed 2026-08-15T17:57:01.229919Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation 52de8219-bcb8-4b5f-aba6-7f9f38499dfb · outbound

This paper cites an unresolved cited work.

Deterministic Almost-Linear-Time Gomory-Hu Trees Unresolved cited work

Reference 37

Resolution: unresolved; raw_fallback, observed 2026-08-15T17:57:01.219355Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation 571b562b-adbd-4d7a-9696-f26cc82892d6 · outbound

This paper cites an unresolved cited work.

Deterministic Almost-Linear-Time Gomory-Hu Trees Unresolved cited work

Reference 42

Resolution: unresolved; raw_fallback, observed 2026-08-15T17:57:01.184683Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation ebcf79a7-94c8-47db-beb2-75f2064a3492 · outbound

This paper cites We now prove Theorem A.2.

Deterministic Almost-Linear-Time Gomory-Hu Trees We now prove Theorem A.2

Reference 43

Resolution: verified fuzzy; raw_fallback, observed 2026-08-15T17:57:01.173239Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation 74080ecc-a39d-45ee-92b7-996746ccc8b9 · outbound

This paper cites an unresolved cited work.

Deterministic Almost-Linear-Time Gomory-Hu Trees Unresolved cited work

Reference 44

Resolution: unresolved; raw_fallback, observed 2026-08-15T17:57:01.161278Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation 61a54ff5-8ffc-43fd-8bbb-6a130547b704 · outbound

This paper cites Consider the flow problem where each vertex v∈ X′ has w(E({v},V \X′)) units of source mass and each vertex u∈ U has ϕ 2d(v) units of sink capacity.

Deterministic Almost-Linear-Time Gomory-Hu Trees Consider the flow problem where each vertex v∈ X′ has w(E({v},V \X′)) units of source mass and each vertex u∈ U has ϕ 2d(v) units of sink capacity

Reference 45

Resolution: verified fuzzy; raw_fallback, observed 2026-08-15T17:57:01.149231Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation 3decdfec-9e6c-4773-bf99-9cf7e776df80 · outbound

This paper cites 10, 23 [HKP07] Ramesh Hariharan, Telikepalli Kavitha, and Debmalya Panigrahi.

Deterministic Almost-Linear-Time Gomory-Hu Trees 10, 23 [HKP07] Ramesh Hariharan, Telikepalli Kavitha, and Debmalya Panigrahi

Reference 527

Resolution: verified fuzzy; raw_fallback, observed 2026-08-15T17:57:01.208598Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation 136182cb-24db-452b-afed-7568724794b8 · outbound

This paper cites Gomory-Hu Trees in Quadratic Time.

Deterministic Almost-Linear-Time Gomory-Hu Trees Gomory-Hu Trees in Quadratic Time

Reference 861

Resolution: unresolved; no resolver link, observed 2026-08-15T17:57:01.018822Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 9bec5417-5eef-4d42-9435-ee0a4aa74ba2 · outbound

This paper cites Multiterminal flows and cuts.

Deterministic Almost-Linear-Time Gomory-Hu Trees Multiterminal flows and cuts

Reference 1994

Resolution: verified exact; raw_fallback, observed 2026-08-15T17:57:01.135833Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Observation a869a7ff-3043-46d2-b948-7d316709b863 · outbound

This paper cites The algorithm closely follows Appendix A of [LP20], which proves an expander decomposition with similar (but incomparable) guarantees.

Deterministic Almost-Linear-Time Gomory-Hu Trees The algorithm closely follows Appendix A of [LP20], which proves an expander decomposition with similar (but incomparable) guarantees

Reference 2021

Resolution: verified fuzzy; raw_fallback, observed 2026-08-15T17:57:01.196674Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-20T06:33:59.587034+00:00.

Pith citing papers

Observation ce05ca54-afaa-43f7-848b-397b69187d5c · inbound

An Online Sparsification Algorithm from the Book cites this paper.

An Online Sparsification Algorithm from the Book Deterministic Almost-Linear-Time Gomory-Hu Trees

Reference 4

Resolution: unresolved; no resolver link, observed 2026-08-01T03:55:26.716428Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.