Buchumschlag

Balancing Weights, Directed Sparsification, and Augmenting Paths

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Li, Jason
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Faster Negative-Weight Shortest Paths and Directed Low-Diameter Decompositions
von: Li, Jason, et al.
Veröffentlicht: (2025)

Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut
von: Cheng, Yu, et al.
Veröffentlicht: (2024)

Deterministic Padded Decompositions and Negative-Weight Shortest Paths
von: Li, Jason
Veröffentlicht: (2025)

Shortcutting for Negative-Weight Shortest Path
von: Li, George Z., et al.
Veröffentlicht: (2025)

Fully Dynamic Spectral Sparsification for Directed Hypergraphs
von: Forster, Sebastian, et al.
Veröffentlicht: (2025)

All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs
von: Anand, Aditya, et al.
Veröffentlicht: (2025)

A Polynomial-Time Algorithm for the Next-to-Shortest Path Problem on Positively Weighted Directed Graphs
von: Chen, Kuowen, et al.
Veröffentlicht: (2025)

A Theory of Spectral CSP Sparsification
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Max-Distance Sparsification for Diversification and Clustering
von: Kumabe, Soh
Veröffentlicht: (2024)

Bootstrapping Dynamic APSP via Sparsification
von: Kyng, Rasmus, et al.
Veröffentlicht: (2024)

Fully Dynamic Spectral Sparsification of Hypergraphs
von: Goranci, Gramoz, et al.
Veröffentlicht: (2025)

Simpler and Faster Directed Low-Diameter Decompositions
von: Li, Jason
Veröffentlicht: (2025)

Tight Paths and Tight Pairs in Weighted Directed Graphs
von: Balcázar, José Luis
Veröffentlicht: (2025)

Efficient Algorithms and New Characterizations for CSP Sparsification
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2024)

Eulerian Graph Sparsification by Effective Resistance Decomposition
von: Jambulapati, Arun, et al.
Veröffentlicht: (2024)

Cut Sparsification and Succinct Representation of Submodular Hypergraphs
von: Kenneth, Yotam, et al.
Veröffentlicht: (2023)

Concurrent Balanced Augmented Trees
von: Wrench, Evan, et al.
Veröffentlicht: (2026)

Fast and Faithful Edge Bundling using Spectral Sparsification
von: Jiang, Xingjue, et al.
Veröffentlicht: (2026)

Near-optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

From Hop Reduction to Sparsification for Negative Length Shortest Paths
von: Quanrud, Kent, et al.
Veröffentlicht: (2025)

Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2025)

A Bottom-Up Algorithm for Negative-Weight SSSP with Integrated Negative Cycle Finding
von: Li, Jason, et al.
Veröffentlicht: (2024)

Engineering Weighted Connectivity Augmentation Algorithms
von: Faraj, Marcelo Fonseca, et al.
Veröffentlicht: (2024)

Improved Directed Expander Decompositions
von: Fleischmann, Henry, et al.
Veröffentlicht: (2025)

Linear-Time Multilevel Graph Partitioning via Edge Sparsification
von: Gottesbüren, Lars, et al.
Veröffentlicht: (2025)

Spectral Sparsification by Deterministic Discrepancy Walk
von: Lau, Lap Chi, et al.
Veröffentlicht: (2024)

Revisiting Directed Disjoint Paths on tournaments (and relatives)
von: Gomes, Guilherme C. M., et al.
Veröffentlicht: (2025)

On Incremental Approximate Shortest Paths in Directed Graphs
von: Górkiewicz, Adam, et al.
Veröffentlicht: (2025)

Near-optimal Hypergraph Sparsification in Insertion-only and Bounded-deletion Streams
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

All-Pairs Shortest Paths with Few Weights per Node
von: Abboud, Amir, et al.
Veröffentlicht: (2025)

An Improved Approximation Algorithm for Maximum Weight 3-Path Packing
von: Zhao, Jingyang, et al.
Veröffentlicht: (2025)

Uniform Sampling of Negative Edge Weights in Shortest Path Networks
von: Geis, Lukas, et al.
Veröffentlicht: (2024)

Additive Sparsification of CSPs
von: Pelleg, Eden, et al.
Veröffentlicht: (2021)

Deterministic Near-Linear Time Minimum Cut in Weighted Graphs
von: Henzinger, Monika, et al.
Veröffentlicht: (2024)

Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Nearly Space-Optimal Graph and Hypergraph Sparsification in Insertion-Only Data Streams
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2025)

Negative-Weight Single-Source Shortest Paths in Near-linear Time
von: Bernstein, Aaron, et al.
Veröffentlicht: (2022)

Simple Sublinear Algorithms for $(Δ+1)$ Vertex Coloring via Asymmetric Palette Sparsification
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
von: Ashvinkumar, Vikrant, et al.
Veröffentlicht: (2024)

A Strong Linear Programming Relaxation for Weighted Tree Augmentation
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2026)