On the public citation graph

Fully Dynamic Maximal Matching in O (log n) Update Time

0 signed · 61 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1007/3-540-57899-4_44openalex-snapshot
Fully dynamic maintenance of vertex cover
inferredcites →https://doi.org/10.1007/pl00009186openalex-snapshot
Average-Case Analysis of Dynamic Graph Algorithms
inferredcites →https://doi.org/10.1016/j.jalgor.2003.12.002openalex-snapshot
Cuckoo hashing
inferredcites →https://doi.org/10.1016/j.tcs.2007.04.040openalex-snapshot
Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
inferredcites →https://doi.org/10.1109/sfcs.1980.12openalex-snapshot
An O(v|v| c |E|) algoithm for finding maximum matching in general graphs
inferredcites →https://doi.org/10.1145/1806689.1806753openalex-snapshot
Maintaining a large matching and a small vertex cover
inferredcites →https://doi.org/10.1145/320211.320215openalex-snapshot
Randomized fully dynamic graph algorithms with polylogarithmic time per operation
inferredcites →https://doi.org/10.1145/502090.502095openalex-snapshot
Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
inferredcites →https://doi.org/10.5555/1283383.1283397openalex-snapshot
Faster dynamic matchings and vertex connectivity

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1007/978-3-030-39219-2_27openalex-snapshot
0-1 Timed Matching in Bipartite Temporal Graphs
inferred← citeshttps://doi.org/10.1007/978-3-032-05294-0_12openalex-snapshot
Algebraic and Dynamic Graph Algorithms
inferred← citeshttps://doi.org/10.1007/978-3-319-28684-6_6openalex-snapshot
Shortest Augmenting Paths for Online Matchings on Trees
inferred← citeshttps://doi.org/10.1007/978-3-319-59250-3_8openalex-snapshot
Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in O(1) Amortized Update Time
inferred← citeshttps://doi.org/10.1007/978-3-662-47666-6_40openalex-snapshot
Maintaining Near-Popular Matchings
inferred← citeshttps://doi.org/10.1007/978-3-662-47672-7_14openalex-snapshot
Fully Dynamic Matching in Bipartite Graphs
inferred← citeshttps://doi.org/10.1007/978-3-662-47672-7_17openalex-snapshot
Design of Dynamic Algorithms via Primal-Dual Method
inferred← citeshttps://doi.org/10.1007/s00224-017-9838-xopenalex-snapshot
Shortest Augmenting Paths for Online Matchings on Trees
inferred← citeshttps://doi.org/10.1007/s00453-019-00630-4openalex-snapshot
Deterministic Dynamic Matching in O(1) Update Time
inferred← citeshttps://doi.org/10.1016/j.procs.2017.05.098openalex-snapshot
Fully-Dynamic Graph Algorithms with Sublinear Time Inspired by Distributed Computing
inferred← citeshttps://doi.org/10.1080/00295450.2020.1843893openalex-snapshot
Scalable Feature Tracking for Finite Element Meshes Demonstrated with a Novel Phase-Field Grain Subdivision Model
inferred← citeshttps://doi.org/10.1109/focs.2013.65openalex-snapshot
Fully Dynamic (1+ e)-Approximate Matchings
inferred← citeshttps://doi.org/10.1109/focs.2014.48openalex-snapshot
Online Bipartite Matching in Offline Time
inferred← citeshttps://doi.org/10.1109/focs.2014.53openalex-snapshot
Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems
inferred← citeshttps://doi.org/10.1109/focs.2016.43openalex-snapshot
Fully Dynamic Maximal Matching in Constant Update Time
inferred← citeshttps://doi.org/10.1109/focs.2016.58openalex-snapshot
Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms
inferred← citeshttps://doi.org/10.1109/focs.2017.92openalex-snapshot
Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time
inferred← citeshttps://doi.org/10.1109/focs57990.2023.00095openalex-snapshot
Dynamic (1+ϵ)-Approximate Matching Size in Truly Sublinear Update Time
inferred← citeshttps://doi.org/10.1109/focs61266.2024.00027openalex-snapshot
Fully Dynamic Matching and Ordered Ruzsa-Szemerédi Graphs
inferred← citeshttps://doi.org/10.1109/icdmw.2016.0092openalex-snapshot
Finding Large Matchings in Semi-Streaming
inferred← citeshttps://doi.org/10.1137/1.9781611973730.54openalex-snapshot
Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching
inferred← citeshttps://doi.org/10.1137/1.9781611973730.82openalex-snapshot
Parameterized Streaming: Maximal Matching and Vertex Cover
inferred← citeshttps://doi.org/10.1137/1.9781611974331.ch50openalex-snapshot
Faster Fully Dynamic Matchings with Small Approximation Ratios
inferred← citeshttps://doi.org/10.1137/1.9781611975031.1openalex-snapshot
Dynamic Algorithms for Graph Coloring
inferred← citeshttps://doi.org/10.1137/1.9781611975482.113openalex-snapshot
Deterministically Maintaining a (2 + ∊ )-Approximate Minimum Vertex Cover in O (1/ ∊ 2 ) Amortized Update Time
inferred← citeshttps://doi.org/10.1137/1.9781611975482.162openalex-snapshot
Expander Decomposition and Pruning: Faster, Stronger, and Simpler
inferred← citeshttps://doi.org/10.1137/1.9781611975482.98openalex-snapshot
Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs
inferred← citeshttps://doi.org/10.1137/1.9781611976465.150openalex-snapshot
Dynamic Set Cover: Improved Amortized and Worst-Case Update Time
inferred← citeshttps://doi.org/10.1137/1.9781611977066.2openalex-snapshot
Maintaining an EDCS in General Graphs: Simpler, Density-Sensitive and with Worst-Case Time Bounds
inferred← citeshttps://doi.org/10.1145/2488608.2488703openalex-snapshot
Simple deterministic algorithms for fully dynamic maximal matching
inferred← citeshttps://doi.org/10.1145/2700206openalex-snapshot
Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
inferred← citeshttps://doi.org/10.1145/2897518.2897568openalex-snapshot
New deterministic approximation algorithms for fully dynamic matching
inferred← citeshttps://doi.org/10.1145/3188745.3188922openalex-snapshot
Fully dynamic maximal independent set with sublinear update time
inferred← citeshttps://doi.org/10.1145/3230819openalex-snapshot
Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
inferred← citeshttps://doi.org/10.1145/3323165.3323202openalex-snapshot
Dynamic Algorithms for the Massively Parallel Computation Model
inferred← citeshttps://doi.org/10.1145/3338529openalex-snapshot
Fully Dynamic Graph Algorithms Inspired by Distributed Computing
inferred← citeshttps://doi.org/10.1145/3350755.3400248openalex-snapshot
A Unified Sparsification Approach for Matching Problems in Graphs of Bounded Neighborhood Independence
inferred← citeshttps://doi.org/10.1145/3357713.3384258openalex-snapshot
Rounding dynamic matchings against an adaptive adversary
inferred← citeshttps://doi.org/10.1145/3564246.3585110openalex-snapshot
On Regularity Lemma and Barriers in Streaming and Dynamic Matching
inferred← citeshttps://doi.org/10.1145/3626183.3659982openalex-snapshot
Parallel Dynamic Maximal Matching
inferred← citeshttps://doi.org/10.1145/3679009openalex-snapshot
Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time
inferred← citeshttps://doi.org/10.1145/3694906.3743313openalex-snapshot
Parallel Batch-Dynamic Maximal Matching with Constant Work per Update
inferred← citeshttps://doi.org/10.1145/3717823.3718153openalex-snapshot
Deterministic Dynamic Maximal Matching in Sublinear Update Time
inferred← citeshttps://doi.org/10.1145/3798129.3800868openalex-snapshot
A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching
inferred← citeshttps://doi.org/10.14232/actacyb.23.3.2018.10openalex-snapshot
DFS is Unsparsable and Lookahead Can Help in Maximal Matching
inferred← citeshttps://doi.org/10.4230/lipics.fsttcs.2012.257openalex-snapshot
Maintaining Approximate Maximum Weighted Matching in Fully Dynamic Graphs
inferred← citeshttps://doi.org/10.4230/lipics.icalp.2021.27openalex-snapshot
Deterministic Rounding of Dynamic Fractional Matchings
inferred← citeshttps://doi.org/10.48550/arxiv.1103.1109openalex-snapshot
Fully dynamic maximal matching in O(log n) update time
inferred← citeshttps://doi.org/10.48550/arxiv.1402.0054openalex-snapshot
Popular conjectures imply strong lower bounds for dynamic problems
inferred← citeshttps://doi.org/10.5555/2884435.2884486openalex-snapshot
Dynamic (1 + ε)-approximate matchings: a density-sensitive approach
inferred← citeshttps://doi.org/10.5555/3310435.3310549openalex-snapshot
(1 + ε-Approximate incremental matching in constant deterministic amortized time
inferred← citeshttps://doi.org/10.7916/d8qf8t2wopenalex-snapshot
Dynamic Algorithms for Shortest Paths and Matching
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.