MAXIMAL MATCHING STABILIZES IN QUADRATIC TIME

被引：20

作者：

TEL, G

机构：

[1] Department of Computer Science, University of Utrecht, 3508 TB Utrecht

来源：

INFORMATION PROCESSING LETTERS | 1994年 / 49卷 / 06期

关键词：

DISTRIBUTED SYSTEMS; MAXIMAL MATCHING; SELF-STABILIZATION; VARIANT FUNCTION;

D O I：

10.1016/0020-0190(94)90098-1

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

By providing an alternative variant function, we show the time complexity of Hsu and Huang's self-stabilizing algorithm for maximal matching to be bounded by 1/2n2 + 2n + 1 steps. We show that the new bound is almost tight by providing an execution with 1/2n2 + n - 2 steps (if n is even).

引用

页码：271 / 272

页数：2