Imagen de Portada

A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Chuzhoy, Julia, Khanna, Sanjeev, Song, Junkai
Formato:	Preprint
Publicado:	2026
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

Maximum Bipartite Matching in $n^{2+o(1)}$ Time via a Combinatorial Algorithm
por: Chuzhoy, Julia, et al.
Publicado: (2024)

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

An $n^{2+o(1)}$ Time Algorithm for Single-Source Negative Weight Shortest Paths
por: Khanna, Sanjeev, et al.
Publicado: (2026)

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

Streaming Maximal Matching with Bounded Deletions
por: Khanna, Sanjeev, et al.
Publicado: (2025)

Faster Algorithms for Global Minimum Vertex-Cut in Directed Graphs
por: Chuzhoy, Julia, et al.
Publicado: (2025)

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

An $\widetilde{O} (n^{3/7})$ Round Parallel Algorithm for Matroid Bases
por: Khanna, Sanjeev, et al.
Publicado: (2026)

On the Parallel Complexity of Finding a Matroid Basis
por: Khanna, Sanjeev, et al.
Publicado: (2025)

Breaking the O(mn)-Time Barrier for Vertex-Weighted Global Minimum Cut
por: Chuzhoy, Julia, et al.
Publicado: (2025)

Optimal Parallel Basis Finding in Graphic and Related Matroids
por: Khanna, Sanjeev, et al.
Publicado: (2025)

Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms
por: Assadi, Sepehr, et al.
Publicado: (2025)

Deterministic Dynamic Maximal Matching in Sublinear Update Time
por: Bernstein, Aaron, et al.
Publicado: (2025)

A Faster Deterministic Algorithm for Kidney Exchange via Representative Set
por: Tian, Kangyi, et al.
Publicado: (2026)

Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness
por: Khanna, Sanjeev, et al.
Publicado: (2025)

A Faster Deterministic Approximation Algorithm for TTP-2
por: Kanaya, Yuga, et al.
Publicado: (2023)

Efficient Algorithms and New Characterizations for CSP Sparsification
por: Khanna, Sanjeev, et al.
Publicado: (2024)

Efficient Deterministic Algorithms for Maximizing Symmetric Submodular Functions
por: Wan, Zongqi, et al.
Publicado: (2024)

A Deterministic Polylogarithmic Competitive Algorithm for Matching with Delays
por: Dufay, Marc, et al.
Publicado: (2025)

Faster Pseudo-Deterministic Minimum Cut
por: Kenneth-Mordoch, Yotam
Publicado: (2026)

Faster Deterministic Streaming Vertex Coloring
por: Chechik, Shiri, et al.
Publicado: (2026)

A Faster Algorithm for Maximum Weight Matching on Unrestricted Bipartite Graphs
por: Kwok, Shawxing
Publicado: (2025)

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

A Theory of Spectral CSP Sparsification
por: Khanna, Sanjeev, et al.
Publicado: (2025)

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

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

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

Fault-Tolerant Distance Oracles Below the $n \cdot f$ Barrier
por: Khanna, Sanjeev, et al.
Publicado: (2026)

Query Complexity of the Metric Steiner Tree Problem
por: Chen, Yu, et al.
Publicado: (2022)

Near-optimal Hypergraph Sparsification in Insertion-only and Bounded-deletion Streams
por: Khanna, Sanjeev, et al.
Publicado: (2025)

Faster Algorithm for Structured John Ellipsoid Computation
por: Cao, Yang, et al.
Publicado: (2022)

A Faster Deterministic Algorithm for Mader's $\mathcal{S}$-Path Packing
por: Iwata, Satoru, et al.
Publicado: (2024)

Simple Algorithms for Fully Dynamic Edge Connectivity
por: Kenneth-Mordoch, Yotam, et al.
Publicado: (2025)

On $b$-Matching and Fully-Dynamic Maximum $k$-Edge Coloring
por: El-Hayek, Antoine, et al.
Publicado: (2023)

On Approximate Fully-Dynamic Matching and Online Matrix-Vector Multiplication
por: Liu, Yang P.
Publicado: (2024)

Simpler O(1) Query Algorithm for Level Ancestors
por: Saxena, Sanjeev
Publicado: (2022)

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

Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs
por: Khanna, Sanjeev, et al.
Publicado: (2024)

Faster ED-String Matching with $k$ Mismatches
por: Gawrychowski, Paweł, et al.
Publicado: (2025)

Simple and Faster Algorithms for Knapsack
por: He, Qizheng, et al.
Publicado: (2023)