Copertina

Fully Dynamic Spectral and Cut Sparsifiers for Directed Graphs

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Zhao, Yibin
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Dynamic Kernel Graph Sparsifiers
di: Cao, Yang, et al.
Pubblicazione: (2022)

Cut-Preserving Vertex Sparsifiers for Planar and Quasi-bipartite Graphs
di: Chen, Yu, et al.
Pubblicazione: (2024)

Fully Dynamic Spectral Sparsification for Directed Hypergraphs
di: Forster, Sebastian, et al.
Pubblicazione: (2025)

Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
di: Khanna, Sanjeev, et al.
Pubblicazione: (2024)

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

Sparsifying Cayley Graphs on Every Group
di: Hsieh, Jun-Ting, et al.
Pubblicazione: (2025)

Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time
di: Jin, Wenyu, et al.
Pubblicazione: (2024)

Fully Dynamic Spectral Sparsification of Hypergraphs
di: Goranci, Gramoz, et al.
Pubblicazione: (2025)

Nearly-Tight Bounds for Flow Sparsifiers in Quasi-Bipartite Graphs
di: Das, Syamantak, et al.
Pubblicazione: (2024)

Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation
di: El-Hayek, Antoine, et al.
Pubblicazione: (2024)

Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity
di: de Vos, Tijn, et al.
Pubblicazione: (2024)

Sparsifying Sums of Positive Semidefinite Matrices
di: Basu, Arpon, et al.
Pubblicazione: (2025)

Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs
di: Ahi, Mridul, et al.
Pubblicazione: (2025)

Improved Tree Sparsifiers in Near-Linear Time
di: Agassy, Daniel, et al.
Pubblicazione: (2025)

Lower Bounds on Flow Sparsifiers with Steiner Nodes
di: Chen, Yu, et al.
Pubblicazione: (2026)

Linear-Sized Spectral Sparsifiers and the Kadison-Singer Problem
di: Paschalidis, Phevos, et al.
Pubblicazione: (2023)

Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems
di: Dughmi, Shaddin, et al.
Pubblicazione: (2025)

Fully Dynamic Algorithms for Coloring Triangle-Free Graphs
di: Assadi, Sepehr, et al.
Pubblicazione: (2026)

Fully Dynamic Matching and Ordered Ruzsa-Szemerédi Graphs
di: Behnezhad, Soheil, et al.
Pubblicazione: (2024)

Near-optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification
di: Khanna, Sanjeev, et al.
Pubblicazione: (2025)

Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut
di: Cheng, Yu, et al.
Pubblicazione: (2024)

Twice-Ramanujan Sparsifiers
di: Batson, Joshua, et al.
Pubblicazione: (2008)

Many Hamiltonians Are Sparsifiable
di: Basu, Arpon, et al.
Pubblicazione: (2026)

Eulerian Graph Sparsification by Effective Resistance Decomposition
di: Jambulapati, Arun, et al.
Pubblicazione: (2024)

Deterministic and Exact Fully-dynamic Minimum Cut of Superpolylogarithmic Size in Subpolynomial Time
di: El-Hayek, Antoine, et al.
Pubblicazione: (2025)

Sketching Cuts in Graphs and Hypergraphs
di: Kogan, Dmitry, et al.
Pubblicazione: (2014)

On Sparsest Cut and Conductance in Directed Polymatroidal Networks
di: Chekuri, Chandra, et al.
Pubblicazione: (2024)

Beyond Spectral Clustering: Probabilistic Cuts for Differentiable Graph Partitioning
di: Ghriss, Ayoub
Pubblicazione: (2025)

Local Max-Cut on Sparse Graphs
di: Schwartzman, Gregory
Pubblicazione: (2023)

Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemeredi Graphs
di: Assadi, Sepehr, et al.
Pubblicazione: (2024)

Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition
di: Chuzhoy, Julia, et al.
Pubblicazione: (2026)

Approximating Directed Minimum Cut and Arborescence Packing via Directed Expander Hierarchies
di: Jiang, Yonggang, et al.
Pubblicazione: (2025)

Unweighted One-Sided Code Sparsifiers and Thin Subgraphs
di: Gharan, Shayan Oveis, et al.
Pubblicazione: (2025)

DTC: Real-Time and Accurate Distributed Triangle Counting in Fully Dynamic Graph Streams
di: Xuan, Wei, et al.
Pubblicazione: (2025)

Streaming Algorithms via Local Algorithms for Maximum Directed Cut
di: Saxena, Raghuvansh R., et al.
Pubblicazione: (2024)

Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds
di: Hwang, Samuel, et al.
Pubblicazione: (2024)

On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets
di: Ghoshal, Suprovat, et al.
Pubblicazione: (2026)

Fully Dynamic Euclidean k-Means
di: Bhattacharya, Sayan, et al.
Pubblicazione: (2025)

Fully Dynamic Algorithms for Chamfer Distance
di: Goranci, Gramoz, et al.
Pubblicazione: (2025)

Fully Dynamic Algorithms for Transitive Reduction
di: Goranci, Gramoz, et al.
Pubblicazione: (2025)