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 条
  • [1] MAXIMAL MATCHING STABILIZES IN QUADRATIC TIME
    TEL, G
    INFORMATION PROCESSING LETTERS, 1994, 49 (06) : 271 - 272
  • [2] Fully dynamic maximal matching in O(log n) update time
    Baswana, Surender
    Gupta, Manoj
    Sen, Sandeep
    2011 IEEE 52ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2011), 2011, : 383 - 392
  • [3] FULLY DYNAMIC MAXIMAL MATCHING IN O(log n) UPDATE TIME
    Baswana, Surender
    Gupta, Manoj
    Sen, Sandeep
    SIAM JOURNAL ON COMPUTING, 2015, 44 (01) : 88 - 113
  • [4] FULLY DYNAMIC MAXIMAL MATCHING IN O(log N) UPDATE TIME (CORRECTED VERSION)
    Baswana, Surender
    Gupta, Manoj
    Sen, Sandeep
    SIAM JOURNAL ON COMPUTING, 2018, 47 (03) : 617 - 650
  • [5] A robust distributed generalized matching protocol that stabilizes in linear time
    Goddard, W
    Hedetniemi, ST
    Jacobs, DR
    Srimani, PK
    23RD INTERNATIONAL CONFERENCE ON DISTRIBUTED COMPUTING SYSTEMS WORKSHOPS, 2003, : 461 - 465
  • [6] AN O(M LOG N)-TIME ALGORITHM FOR THE MAXIMAL PLANAR SUBGRAPH PROBLEM
    CAI, JZ
    HAN, XF
    TARJAN, RE
    SIAM JOURNAL ON COMPUTING, 1993, 22 (06) : 1142 - 1162
  • [7] Fully Dynamic Maximal Matching in Constant Update Time
    Solomon, Shay
    2016 IEEE 57TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2016, : 325 - 334
  • [8] Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width
    de Menibus, Benjamin Hellouin
    Uno, Takeaki
    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2011, 2011, 6648 : 483 - 494
  • [9] Maximal Assortative Matching and Maximal Dissortative Matching for Complex Network Graphs
    Meghanathan, Natarajan
    COMPUTER JOURNAL, 2016, 59 (05): : 667 - 684
  • [10] AN O(EVLOGV) ALGORITHM FOR FINDING A MAXIMAL WEIGHTED MATCHING IN GENERAL GRAPHS
    GALIL, Z
    MICALI, S
    GABOW, H
    SIAM JOURNAL ON COMPUTING, 1986, 15 (01) : 120 - 130
12345