Faster cut sparsification of weighted graphs
From MaRDI portal
Publication:2696277
DOI10.1007/s00453-022-01053-4OpenAlexW4308041253MaRDI QIDQ2696277
Tijn de Vos, Sebastian Forster
Publication date: 11 April 2023
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2112.03120
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the shortest spanning subtree of a graph and the traveling salesman problem
- Generating the maximum of independent identically distributed random variables
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- On sparse spanners of weighted graphs
- Random Sampling in Cut, Flow, and Network Design Problems
- On Sketching Quadratic Forms
- Spectral Sparsification of Graphs
- Undirected single-source shortest paths with positive integer weights in linear time
- Graph spanners
- Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
- Efficiency of a Good But Not Linear Set Union Algorithm
- A randomized linear-time algorithm to find minimum spanning trees
- A new approach to the minimum cut problem
- Efficient Algorithms for Constructing Very Sparse Spanners and Emulators
- Twice-Ramanujan Sparsifiers
- An SDP-based algorithm for linear-sized spectral sparsification
- Faster Algorithms for Edge Connectivity via Random 2-Out Contractions
- A General Framework for Graph Sparsification
- Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
- Towards Resistance Sparsifiers
- A general framework for graph sparsification
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- Graph Sparsification by Effective Resistances
