Buchumschlag

Space Complexity of Vertex Connectivity Oracles

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Pettie, Seth, Saranurak, Thatchaphol, Yin, Longhui
Format:	Preprint
Veröffentlicht:	2022
Schlagworte:	Data Structures and Algorithms Combinatorics
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies
von: Long, Yaowei, et al.
Veröffentlicht: (2024)

Connectivity Oracle Under Vertex Failures by Shortcutting Unbreakable Decomposition
von: Li, Xizhe, et al.
Veröffentlicht: (2026)

Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness
von: Jiang, Yonggang, et al.
Veröffentlicht: (2025)

Dynamic Deterministic Constant-Approximate Distance Oracles with $n^ε$ Worst-Case Update Time
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2024)

Near-Optimal Fault-Tolerant Strong Connectivity Preservers
von: Hoppenworth, Gary, et al.
Veröffentlicht: (2025)

Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries
von: Anand, Aditya, et al.
Veröffentlicht: (2024)

Length-Constrained Directed Expander Decomposition and Length-Constrained Vertex-Capacitated Flow Shortcuts
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2025)

Finding Most Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time
von: Hua, Kevin, et al.
Veröffentlicht: (2024)

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)

Decremental $(1+ε)$-Approximate Maximum Eigenvector: Dynamic Power Method
von: Adil, Deeksha, et al.
Veröffentlicht: (2024)

Local Sherman's Algorithm for Multi-commodity Flow
von: Li, Jason, et al.
Veröffentlicht: (2025)

Computing Vertex and Edge Connectivity of Graphs Embedded with Crossings
von: Biedl, Therese, et al.
Veröffentlicht: (2024)

Expander Decomposition with Almost Optimal Overhead
von: Bansal, Nikhil, et al.
Veröffentlicht: (2026)

DAG Projections: Reducing Distance and Flow Problems to DAGs
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2026)

Reducing Shortcut and Hopset Constructions to Shallow Graphs
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2025)

Dynamic $(1+ε)$-Approximate Matching Size in Truly Sublinear Update Time
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2023)

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

Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time
von: Meierhans, Simon, et al.
Veröffentlicht: (2025)

Cactus Representation of Minimum Cuts: Derandomize and Speed up
von: He, Zhongtian, et al.
Veröffentlicht: (2024)

On Computing Vertex Connectivity of 1-Plane Graphs
von: Biedl, Therese, et al.
Veröffentlicht: (2022)

Reviving Thorup's Shortcut Conjecture
von: Bernstein, Aaron, et al.
Veröffentlicht: (2025)

Fully Dynamic Exact Edge Connectivity in Sublinear Time
von: Goranci, Gramoz, et al.
Veröffentlicht: (2023)

Matroid Intersection under Minimum Rank Oracle
von: Bárász, Mihály, et al.
Veröffentlicht: (2024)

Chasing Positive Bodies
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2023)

Deterministic Dynamic Maximal Matching in Sublinear Update Time
von: Bernstein, Aaron, et al.
Veröffentlicht: (2025)

A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge Failures
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2026)

Approximating Small Sparse Cuts
von: Anand, Aditya, et al.
Veröffentlicht: (2024)

Approximating Directed Minimum Cut and Arborescence Packing via Directed Expander Hierarchies
von: Jiang, Yonggang, et al.
Veröffentlicht: (2025)

Complexity of the (Connected) Cluster Vertex Deletion problem on $H$-free graphs
von: Le, Hoang-Oanh, et al.
Veröffentlicht: (2024)

A Unified Construction of Streaming Sketches via the Lévy-Khintchine Representation Theorem
von: Pettie, Seth, et al.
Veröffentlicht: (2024)

Universal Perfect Samplers for Incremental Streams
von: Pettie, Seth, et al.
Veröffentlicht: (2024)

A faster algorithm for Vertex Cover parameterized by solution size
von: Harris, David G., et al.
Veröffentlicht: (2022)

Maximum Flow by Augmenting Paths in $n^{2+o(1)}$ Time
von: Bernstein, Aaron, et al.
Veröffentlicht: (2024)

Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal
von: Chen, Daoyuan, et al.
Veröffentlicht: (2024)

Disjoint Paths in Expanders in Deterministic Almost-Linear Time via Hypergraph Perfect Matching
von: Bucić, Matija, et al.
Veröffentlicht: (2025)

Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth
von: Ashvinkumar, Vikrant, et al.
Veröffentlicht: (2026)

Connectivity Oracles for Predictable Vertex Failures
von: Hu, Bingbing, et al.
Veröffentlicht: (2023)

Connected Partitions via Connected Dominating Sets
von: Niklanovits, Aikaterini, et al.
Veröffentlicht: (2025)

Parallel $(1+ε)$-Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2025)

Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems
von: Bernstein, Aaron, et al.
Veröffentlicht: (2025)