(1 + ε)-Approximate Incremental Matching in Constant Deterministic Amortized Time
(1 + ε)-Approximate Incremental Matching in Constant Deterministic Amortized Time
复制标题
(1 + ε)-恒定确定性摊余时间内的近似增量匹配
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Shay Solomon
中科院分区：
文献类型：
--
作者：
F. Grandoni;S. Leonardi;P. Sankowski;Chris Schwiegelshohn;Shay Solomon
我们研究增量设置中的匹配问题，其中给定一系列边缘插入，并旨在以较小的更新时间维持图的接近最大基数匹配。我们提出了一种确定性算法，对于任何常数 ε > 0，保持 (1 + ε )- 近似匹配，每次插入的摊销更新时间恒定。
We study the matching problem in the incremental setting, where we are given a sequence of edge insertions and aim at maintaining a near-maximum cardinality matching of the graph with small update time. We present a deterministic algorithm that, for any constant ε > 0, maintains a (1 + ε )- approximate matching with constant amortized update time per insertion.
核心集满足 EDCS：海量图上的匹配和顶点覆盖算法
DOI：
--
发表时间：
2019
期刊：
SODA 2019
影响因子：
--
作者：
Assadi, S.
Batenai
通讯作者：
Assadi, S.
Batenai