Design networks with bounded pairwise distance

DOI10.1145/301250.301447zbMath1345.90032OpenAlexW2022092881MaRDI QIDQ2819606

Sanjeev Khanna, Yevgeniy Dodis

Publication date: 29 September 2016

Published in: Proceedings of the thirty-first annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Communication networks in operations research (90B18) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (max. 100)

Augmenting weighted graphs to establish directed point-to-point connectivity ⋮ On minimum generalized Manhattan connections ⋮ Tree-decompositions with bags of small diameter ⋮ Fast Algorithms for Diameter-Optimally Augmenting Paths ⋮ Spanners for bounded tree-length graphs ⋮ A Polynomial-Time Algorithm for Outerplanar Diameter Improvement ⋮ A polynomial-time algorithm for outerplanar diameter improvement ⋮ Online Buy-at-Bulk Network Design ⋮ A Spectral Approach to Network Design ⋮ Reachability Preservers: New Extremal Bounds and Approximation Algorithms ⋮ Augmenting graphs to minimize the radius ⋮ Improved approximation algorithms for directed Steiner forest ⋮ An ETH-tight algorithm for bidirected Steiner connectivity ⋮ Unnamed Item ⋮ Approximating node-connectivity augmentation problems ⋮ Improved approximation algorithms for label cover problems ⋮ The subdivision-constrained routing requests problem ⋮ ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network ⋮ Fast Algorithms for Diameter-Optimally Augmenting Paths and Trees ⋮ Tight approximation algorithm for connectivity augmentation problems ⋮ Augmenting graphs to minimize the diameter ⋮ Shortcutting directed and undirected networks with a degree constraint ⋮ Improved Approximation for the Directed Spanner Problem ⋮ Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs ⋮ Tree spanners in planar graphs ⋮ Approximating survivable networks with \(\beta \)-metric costs ⋮ Unnamed Item ⋮ Approximability of unsplittable shortest path routing problems ⋮ Augmenting forests to meet odd diameter requirements ⋮ Bulk-robust combinatorial optimization ⋮ Mixed covering of trees and the augmentation problem with odd diameter constraints ⋮ Approximating Steiner Networks with Node Weights ⋮ Inapproximability of survivable networks ⋮ Complexity of the Steiner Network Problem with Respect to the Number of Terminals ⋮ Improved approximability and non-approximability results for graph diameter decreasing problems ⋮ Parameterized Approximation Algorithms for Bidirected Steiner Network Problems ⋮ Unnamed Item ⋮ Distributed Distance-Bounded Network Design Through Distributed Convex Programming

This page was built for publication: Design networks with bounded pairwise distance