The first polynomial self-stabilizing 1-maximal matching algorithm for general graphs

DOI10.1016/J.TCS.2019.02.031MaRDI QIDQ2420642zbMATH OpenOpenAlexWikidataFDO

Authors Johanne Cohen, Jonas Lefèvre, Khaled Maâmra, George Manoussakis, Laurence Pilard

Publication date 6 June 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2019.02.031

zbMATH Keywords

self-stabilization\(\frac{2}{3}\)-approximation1-maximal matching

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Polynomial self-stabilizing maximum matching algorithm with approximation ratio 2/3
• An efficient silent self-stabilizing 1-maximal matching algorithm under distributed daemon for arbitrary networks
• An efficient silent self-stabilizing algorithm for 1-maximal matching in anonymous networks

Cites work

• scientific article; zbMATH DE number 1304326 (Why is no real title available?)
• A new analysis of a self-stabilizing maximum weight matching algorithm with approximation ratio 2
• A self-stabilizing \(\frac23\)-approximation algorithm for the maximum matching problem
• A self-stabilizing algorithm for maximal matching
• A self-stabilizing algorithm for maximal matching in anonymous networks
• A simple approximation algorithm for the weighted matching problem
• A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• An efficient silent self-stabilizing 1-maximal matching algorithm under distributed daemon without global identifiers
• An efficient silent self-stabilizing algorithm for 1-maximal matching in anonymous networks
• Brief Announcement
• Dynamic and self-stabilizing distributed matching
• Dynamic load balancing by random matchings
• Maximal matching stabilizes in time \(O(m)\)
• Maximum matching for anonymous trees with constant space per process
• On the stability of dynamic diffusion load balancing
• Self-stabilization

Cited in

(3)

• A new self-stabilizing algorithm for maximal \(p\)-star decomposition of general graphs
• Polynomial self-stabilizing maximum matching algorithm with approximation ratio 2/3
• Communication efficient self-stabilizing leader election

This page was built for publication: The first polynomial self-stabilizing 1-maximal matching algorithm for general graphs

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