Imagen de Portada

Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Blikstad, Joakim, Jiang, Yonggang, Mukhopadhyay, Sagnik, Yingchareonthawornchai, Sorrachai
Formato:	Preprint
Publicado:	2025
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs
por: Fischer, Olivier, et al.
Publicado: (2025)

Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness
por: Jiang, Yonggang, et al.
Publicado: (2025)

Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth
por: Koh, Zhuan Khye, et al.
Publicado: (2024)

Hardness Amplification for Dynamic Binary Search Trees
por: Jiang, Shunhua, et al.
Publicado: (2024)

Parallel Small Vertex Connectivity in Near-Linear Work and Polylogarithmic Depth
por: Jiang, Yonggang, et al.
Publicado: (2025)

Online Edge Coloring is (Nearly) as Easy as Offline
por: Blikstad, Joakim, et al.
Publicado: (2024)

A Little Clairvoyance Is All You Need
por: Gupta, Anupam, et al.
Publicado: (2025)

A Simpler Analysis for $\varepsilon$-Clairvoyant Flow Time Scheduling
por: Gupta, Anupam, et al.
Publicado: (2026)

Efficient Matroid Intersection via a Batch-Update Auction Algorithm
por: Blikstad, Joakim, et al.
Publicado: (2024)

Shortcuts and Transitive-Closure Spanners Approximation
por: Chalermsook, Parinya, et al.
Publicado: (2025)

Deterministic Edge Coloring with few Colors in CONGEST
por: Blikstad, Joakim, et al.
Publicado: (2026)

Near-Optimal Vertex Fault-Tolerant Labels for Steiner Connectivity
por: Bhanja, Koustav, et al.
Publicado: (2025)

Online Edge Coloring: Sharp Thresholds
por: Blikstad, Joakim, et al.
Publicado: (2025)

Deterministic Online Bipartite Edge Coloring
por: Blikstad, Joakim, et al.
Publicado: (2024)

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

New Oracles and Labeling Schemes for Vertex Cut Queries
por: Jiang, Yonggang, et al.
Publicado: (2025)

Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs
por: Bernstein, Aaron, et al.
Publicado: (2025)

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

ShockHash: Near Optimal-Space Minimal Perfect Hashing Beyond Brute-Force
por: Lehmann, Hans-Peter, et al.
Publicado: (2023)

Perfect Simulation of Las Vegas Algorithms via Local Computation
por: Fu, Xinyu, et al.
Publicado: (2023)

Near-Optimal Dimension Reduction for Facility Location
por: Huang, Lingxiao, et al.
Publicado: (2024)

An Almost Quadratic Vertex Kernel for Subset Feedback Arc Set in Tournaments
por: Bai, Tian
Publicado: (2025)

Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
por: Haeupler, Bernhard, et al.
Publicado: (2025)

Near-Optimal Trace Reconstruction for Mildly Separated Strings
por: Aamand, Anders, et al.
Publicado: (2024)

Near-Optimal Fault-Tolerant Strong Connectivity Preservers
por: Hoppenworth, Gary, et al.
Publicado: (2025)

Greedy Algorithms for Shortcut Sets and Hopsets
por: Bals, Ben, et al.
Publicado: (2025)

9/7-Approximation for Two-Edge-Connectivity and Two-Vertex-Connectivity
por: Çivril, Ali
Publicado: (2024)

Approximating Directed Connectivity in Almost-Linear Time
por: Quanrud, Kent
Publicado: (2025)

An Optimal Algorithm for Stochastic Vertex Cover
por: Brand, Jan van den, et al.
Publicado: (2026)

The Connected k-Vertex One-Center Problem on Graphs
por: Zhang, Jingru
Publicado: (2024)

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

Expander Decomposition with Almost Optimal Overhead
por: Bansal, Nikhil, et al.
Publicado: (2026)

Almost-Optimal Sublinear Additive Spanners
por: Tan, Zihan, et al.
Publicado: (2023)

A (Very) Nearly Optimal Sketch for $k$-Edge Connectivity Certificates
por: Sawettamalya, Pachara, et al.
Publicado: (2025)

Space Complexity of Vertex Connectivity Oracles
por: Pettie, Seth, et al.
Publicado: (2022)

Connectivity Oracle Under Vertex Failures by Shortcutting Unbreakable Decomposition
por: Li, Xizhe, et al.
Publicado: (2026)

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

Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies
por: Long, Yaowei, et al.
Publicado: (2024)

A Fast Approximation Algorithm for the Minimum Balanced Vertex Separator in a Graph
por: Kolmogorov, Vladimir, et al.
Publicado: (2026)

A Unified Approach for Approximating 2-Edge-Connected Spanning Subgraph and 2-Vertex-Connected Spanning Subgraph
por: Çivril, Ali
Publicado: (2023)