Maximal matching stabilizes in time O(m)

被引：25
|
作者：
Hedetniemi, ST [1 ]
Jacobs, DP [1 ]
Srimani, PK [1 ]
机构：
[1] Clemson Univ, Dept Comp Sci, Clemson, SC 29634 USA
来源：
INFORMATION PROCESSING LETTERS | 2001年 / 80卷 / 05期
关键词：
analysis of algorithms; matching; self-stabilizing;
D O I：
10.1016/S0020-0190(01)00171-5
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
On a network having m edges and n nodes, Hsu and Huang's self-stabilizing algorithm for maximal matching stabilizes in at most 2m + n moves. (C) 2001 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：221 / 223
页数：3
相关论文
共 50 条
  • [11] ELASTIC, MAXIMAL MATCHING
    MITRA, RS
    MURTHY, NN
    PATTERN RECOGNITION, 1991, 24 (08) : 747 - 753
  • [12] MAXIMAL MATCHING PROBLEM
    UHRY, JP
    REVUE FRANCAISE D AUTOMATIQUE INFORMATIQUE RECHERCHE OPERATIONNELLE, 1975, 9 (NV3): : 13 - 20
  • [13] Distributed Maximal Matching and Maximal Independent Set on Hypergraphs
    Balliu, Alkida
    Brandt, Sebastian
    Kuhn, Fabian
    Olivetti, Dennis
    PROCEEDINGS OF THE 2023 ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SODA, 2023, : 2632 - 2676
  • [14] AN O(1) TIME ALGORITHM FOR STRING MATCHING
    CHEN, GH
    INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 1992, 42 (3-4) : 185 - 191
  • [15] Maximal Matching for Double Auction
    Zhao, Dengji
    Zhang, Dongmo
    Khan, Md
    Perrussel, Laurent
    AI 2010: ADVANCES IN ARTIFICIAL INTELLIGENCE, 2010, 6464 : 516 - +
  • [16] Parallel Dynamic Maximal Matching
    Ghaffari, Mohsen
    Trygub, Anton
    PROCEEDINGS OF THE 36TH ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES, SPAA 2024, 2024, : 427 - 437
  • [17] Maximal matching polytope in trees
    Tural, Mustafa Kemal
    OPTIMIZATION METHODS & SOFTWARE, 2016, 31 (03): : 471 - 478
  • [18] Maximum Cardinality f-Matching in Time O(n2/3m)
    Gabow, Harold n.
    ACM TRANSACTIONS ON ALGORITHMS, 2025, 21 (01)
  • [19] The Time Complexity of Hsu and Huang's Self-Stabilizing Maximal Matching Algorithm
    Kimoto, Masahiro
    Tsuchiya, Tatsuhiro
    Kikuno, Tohru
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2010, E93D (10) : 2850 - 2853
  • [20] AN O(N) TIME ALGORITHM FOR MAXIMUM MATCHING ON COGRAPHS
    YU, MS
    YANG, CH
    INFORMATION PROCESSING LETTERS, 1993, 47 (02) : 89 - 93
12345