Image de couverture de livre

Unbreakable Decomposition in Close-to-Linear Time

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Anand, Aditya, Lee, Euiwoong, Li, Jason, Long, Yaowei, Saranurak, Thatchaphol
Format:	Preprint
Publié:	2024
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Connectivity Oracle Under Vertex Failures by Shortcutting Unbreakable Decomposition
par: Li, Xizhe, et autres
Publié: (2026)

Approximating Small Sparse Cuts
par: Anand, Aditya, et autres
Publié: (2024)

All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs
par: Anand, Aditya, et autres
Publié: (2025)

Dynamic Deterministic Constant-Approximate Distance Oracles with $n^ε$ Worst-Case Update Time
par: Haeupler, Bernhard, et autres
Publié: (2024)

Length-Constrained Directed Expander Decomposition and Length-Constrained Vertex-Capacitated Flow Shortcuts
par: Haeupler, Bernhard, et autres
Publié: (2025)

Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies
par: Long, Yaowei, et autres
Publié: (2024)

Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries
par: Anand, Aditya, et autres
Publié: (2024)

Local Sherman's Algorithm for Multi-commodity Flow
par: Li, Jason, et autres
Publié: (2025)

A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge Failures
par: Haeupler, Bernhard, et autres
Publié: (2026)

Approximating Directed Minimum Cut and Arborescence Packing via Directed Expander Hierarchies
par: Jiang, Yonggang, et autres
Publié: (2025)

Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
par: Haeupler, Bernhard, et autres
Publié: (2025)

Expander Decomposition with Almost Optimal Overhead
par: Bansal, Nikhil, et autres
Publié: (2026)

Parallel $(1+ε)$-Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work
par: Haeupler, Bernhard, et autres
Publié: (2025)

Finding Most Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time
par: Hua, Kevin, et autres
Publié: (2024)

Separating $k$-Median from the Supplier Version
par: Anand, Aditya, et autres
Publié: (2024)

Decremental $(1+ε)$-Approximate Maximum Eigenvector: Dynamic Power Method
par: Adil, Deeksha, et autres
Publié: (2024)

Dynamic $(1+ε)$-Approximate Matching Size in Truly Sublinear Update Time
par: Bhattacharya, Sayan, et autres
Publié: (2023)

Disjoint Paths in Expanders in Deterministic Almost-Linear Time via Hypergraph Perfect Matching
par: Bucić, Matija, et autres
Publié: (2025)

Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal
par: Chen, Daoyuan, et autres
Publié: (2024)

Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time
par: Meierhans, Simon, et autres
Publié: (2025)

Deterministic Almost-Linear-Time Gomory-Hu Trees
par: Abboud, Amir, et autres
Publié: (2025)

Deterministic Dynamic Maximal Matching in Sublinear Update Time
par: Bernstein, Aaron, et autres
Publié: (2025)

DAG Projections: Reducing Distance and Flow Problems to DAGs
par: Haeupler, Bernhard, et autres
Publié: (2026)

Reducing Shortcut and Hopset Constructions to Shallow Graphs
par: Haeupler, Bernhard, et autres
Publié: (2025)

Near-Optimal Fault-Tolerant Strong Connectivity Preservers
par: Hoppenworth, Gary, et autres
Publié: (2025)

Maximum Flow by Augmenting Paths in $n^{2+o(1)}$ Time
par: Bernstein, Aaron, et autres
Publié: (2024)

Cactus Representation of Minimum Cuts: Derandomize and Speed up
par: He, Zhongtian, et autres
Publié: (2024)

Space Complexity of Vertex Connectivity Oracles
par: Pettie, Seth, et autres
Publié: (2022)

Low-Step Multi-Commodity Flow Emulators
par: Haeupler, Bernhard, et autres
Publié: (2024)

Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs
par: Bernstein, Aaron, et autres
Publié: (2025)

Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT
par: Anand, Aditya, et autres
Publié: (2025)

Chasing Positive Bodies
par: Bhattacharya, Sayan, et autres
Publié: (2023)

Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness
par: Jiang, Yonggang, et autres
Publié: (2025)

Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth
par: Ashvinkumar, Vikrant, et autres
Publié: (2026)

Fully Dynamic Exact Edge Connectivity in Sublinear Time
par: Goranci, Gramoz, et autres
Publié: (2023)

Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems
par: Bernstein, Aaron, et autres
Publié: (2025)

Facility Location on High-dimensional Euclidean Spaces
par: Lee, Euiwoong, et autres
Publié: (2025)

Complexity of Local Search for CSPs Parameterized by Constraint Difference
par: Anand, Aditya, et autres
Publié: (2025)

1.64-Approximation for Chromatic Correlation Clustering via Chromatic Cluster LP
par: Lee, Dahoon, et autres
Publié: (2025)

Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering
par: Fan, Chenglin, et autres
Publié: (2025)