Maximal matching stabilizes in time \(O(m)\)
From MaRDI portal
Publication:1607119
DOI10.1016/S0020-0190(01)00171-5zbMath1003.68004OpenAlexW2070274621MaRDI QIDQ1607119
Pradip K. Srimani, David P. Jacobs, Stephen T. Hedetniemi
Publication date: 25 July 2002
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0020-0190(01)00171-5
Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10)
Related Items (12)
A self-stabilizing algorithm for \(b\)-matching ⋮ Self-stabilizing algorithms for minimal dominating sets and maximal independent sets ⋮ The first polynomial self-stabilizing 1-maximal matching algorithm for general graphs ⋮ Self-stabilizing Cuts in Synchronous Networks ⋮ A self-stabilizing algorithm for the median problem in partial rectangular grids and their relatives ⋮ A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs ⋮ A self-stabilizing algorithm for cut problems in synchronous networks ⋮ A self-stabilizing \(\frac23\)-approximation algorithm for the maximum matching problem ⋮ A new analysis of a self-stabilizing maximum weight matching algorithm with approximation ratio 2 ⋮ A new self-stabilizing maximal matching algorithm ⋮ Self-Stabilizing Domination Algorithms ⋮ A new self-stabilizing algorithm for maximal \(p\)-star decomposition of general graphs
Cites Work
This page was built for publication: Maximal matching stabilizes in time \(O(m)\)
