Multi-priority graph sparsification

DOI10.1007/978-3-031-34347-6_1arXiv2301.12563OpenAlexW4379117687MaRDI QIDQ6182885

Faryad Darabi Sahneh, Keaton Hamm, Reyan Ahmed, Mohammad Javad Latifi Jebelli, Stephen G. Kobourov, Richard Spence

Publication date: 22 December 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

graph spannersapproximation algorithmssparsification

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Unnamed Item
• On sparse spanners of weighted graphs
• New pairwise spanners
• Graph spanners: a tutorial review
• Approximating subset \(k\)-connectivity problems
• Improved approximation algorithms for the quality of service multicast tree problem
• On additive spanners in weighted graphs with local error
• Approximation algorithms for priority Steiner tree problems
• A subset spanner for Planar graphs, with application to subset TSP
• An Improved Approximation Algorithm for Minimum-Cost Subset k-Connectivity
• Additive Spanners: A Simple Construction
• Additive spanners and (α, β)-spanners
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• Modeling and Heuristic Worst-Case Performance Analysis of the Two-Level Network Design Problem
• Near-Optimal Light Spanners
• Error Amplification for Pairwise Spanner Lower Bounds
• The 4/3 Additive Spanner Exponent Is Tight
• On the approximability of some network design problems
• Multi-Level Steiner Trees.
• A PTAS for subset TSP in minor-free graphs
• Approximating Minimum Cost Connectivity Problems via Uncrossable Bifamilies and Spider-Cover Decompositions
• Steiner Tree Approximation via Iterative Randomized Rounding
• New Additive Spanners
• New Results on Linear Size Distance Preservers

This page was built for publication: Multi-priority graph sparsification