Maximal matching stabilizes in time O(m)

DOI10.1016/S0020-0190(01)00171-5MaRDI QIDQ1607119zbMATH OpenOpenAlexFDO

Authors David P. Jacobs, Pradip K. Srimani, 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

zbMATH Keywords

self-stabilizing algorithm

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A self-stabilizing algorithm for maximal matching
• Maximal matching stabilizes in quadratic time

Cited in

(11)

• A self-stabilizing algorithm for b-matching
• A new self-stabilizing algorithm for maximal \(p\)-star decomposition of general graphs
• The first polynomial self-stabilizing 1-maximal matching algorithm for general graphs
• A self-stabilizing algorithm for the median problem in partial rectangular grids and their relatives
• Self-Stabilizing Domination Algorithms
• Self-stabilizing Cuts in Synchronous Networks
• Self-stabilizing algorithms for minimal dominating sets and maximal independent sets
• A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs
• A self-stabilizing 23-approximation algorithm for the maximum matching problem
• A new analysis of a self-stabilizing maximum weight matching algorithm with approximation ratio 2
• A self-stabilizing algorithm for cut problems in synchronous networks

This page was built for publication: Maximal matching stabilizes in time \(O(m)\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1607119)