Skip to search boxSkip to navigationSkip to main content

Sparse Spanners with Small Distance and Congestion Stretches

Scholary Output:
Chapter in Book/Report/Conference proceeding
Conference contribution
Research

Open access

Related Event

Title

36th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2024

Event type

Conference

Date

06/17/2024 - 06/21/2024

Location

NantesFrance

Abstract

<p>Given a graph G, a classical problem in graph theory is the construction of a spanner H - a sparse subgraph of G that closely approximates the distances between nodes in G. The distance stretch∼α of H is the factor of how much the distances in H increase versus G. Here, we consider sparse spanner constructions that can also preserve the node congestion of routing problems in G. The congestion stretch β of H is the factor of how much the (smallest) congestion of a routing problem increases in H versus G. We introduce the notion of (α, β)-DC-spanner (i.e., a Distance-Congestion-spanner) that simultaneously controls the stretches for distance and congestion. We show that for expander graphs with n nodes, there is a (3, O(log n))-DC-spanner with O(n5/3) edges. We also examine "-regular graphs with Δ≥ n2/3, where we show how to obtain a (3, O(Δg... log n))-DC-spanner with O(n5/3 log2n) edges. Finally, we show that there is a graph such that any optimal size 3-distance spanner has ω(n7/6) edges and is a (3, ω(n1/6))-DC-spanner.</p>

Publication Information

Output type

Scholary Output:
Chapter in Book/Report/Conference proceeding
Conference contribution
Research

Original language

English (US)

Pages from-to (Number of pages)

Pages 383-393 (11 pages)

Publication milestones

  • Published - 06/17/2024

Publication status

Published - 06/17/2024

Publisher

Association for Computing Machinery

Publication series

  • Publication series name: Annual ACM Symposium on Parallelism in Algorithms and Architectures
    ISSN (Print): 1548-6109

ISBN (Electronic)

9798400704161

Publication IDs

  • Scopus: 85197377760

Host publication title

SPAA 2024 - Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures

Publication metrics

Metrics

Fractional count
3
Fractional count
1
Fractional count
3
Fractional count
1

Funding Details

This paper is partly supported by NSF grant CNS-2131538.
FunderFunding number
NSF
CNS-2131538