Multi-priority graph sparsification

DOI10.1007/978-3-031-34347-6_1MaRDI QIDQ6182885zbMATH OpenOpenAlexFDO

Authors Reyan Ahmed, Keaton Hamm, Stephen G. Kobourov, Mohammad Javad Latifi Jebelli, Faryad Darabi Sahneh, 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

approximation algorithmsgraph spannerssparsification

Mathematics Subject Classification ID

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

Abstract: A emph{sparsification} of a given graph $G$ is a sparser graph (typically a subgraph) which aims to approximate or preserve some property of $G$. Examples of sparsifications include but are not limited to spanning trees, Steiner trees, spanners, emulators, and distance preservers. Each vertex has the same priority in all of these problems. However, real-world graphs typically assign different ``priorities or ``levels to different vertices, in which higher-priority vertices require higher-quality connectivity between them. Multi-priority variants of the Steiner tree problem have been studied in prior literature but this generalization is much less studied for other sparsification problems. In this paper, we define a generalized multi-priority problem and present a rounding-up approach that can be used for a variety of graph sparsifications. Our analysis provides a systematic way to compute approximate solutions to multi-priority variants of a wide range of graph sparsification problems given access to a single-priority subroutine.

Recommendations

• Approximation and Online Algorithms
• Priority algorithms for graph optimization problems
• A general framework for graph sparsification
• A general framework for graph sparsification
• scientific article; zbMATH DE number 1981892
• scientific article; zbMATH DE number 139775
• Graph optimization for dimensionality reduction with sparsity constraints
• Sparsification—a technique for speeding up dynamic graph algorithms
• Sparsity. Graphs, structures, and algorithms
• Priority-Consistent Graphs

Cites work

• A PTAS for subset TSP in minor-free graphs
• A subset spanner for Planar graphs, with application to subset TSP
• Additive spanners and \(({\alpha}, {\beta})\)-spanners
• Additive spanners: a simple construction
• An improved approximation algorithm for minimum-cost subset k-connectivity (extended abstract)
• Approximating Minimum Cost Connectivity Problems via Uncrossable Bifamilies and Spider-Cover Decompositions
• Approximating subset \(k\)-connectivity problems
• Approximation algorithms for priority Steiner tree problems
• Error Amplification for Pairwise Spanner Lower Bounds
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• Graph spanners: a tutorial review
• scientific article; zbMATH DE number 7774272 (Why is no real title available?)
• Improved approximation algorithms for the quality of service multicast tree problem
• Modeling and Heuristic Worst-Case Performance Analysis of the Two-Level Network Design Problem
• Multi-Level Steiner Trees.
• Near-optimal light spanners
• New additive spanners
• New pairwise spanners
• New results on linear size distance preservers
• On additive spanners in weighted graphs with local error
• On sparse spanners of weighted graphs
• On the approximability of some network design problems
• Steiner tree approximation via iterative randomized rounding
• The 4/3 additive spanner exponent is tight

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6182885)