An algorithm for computing the matching capacity

DOI10.1016/J.AML.2004.02.009MaRDI QIDQ2484637zbMATH OpenOpenAlexFDO

Authors Suren Arzumanyan

Publication date 1 August 2005

Published in Applied Mathematics Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.aml.2004.02.009

Mathematics Subject Classification ID

Channel models (including quantum) in information and communication theory (94A40)

Review text

The author has studied an iterative method of computing the matching capacity of a bipartite graph in which each vertex of degree two or more is adjacent to at least one vertex of degree one. Further, the author has proved its exponentially fast convergence.

Recommendations

• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• scientific article; zbMATH DE number 67678
• Faster scaling algorithms for general graph matching problems
• On the maximum 2-1 matching
• An efficient algorithm for the bipartite matching problem

Cites work

• scientific article; zbMATH DE number 3908323 (Why is no real title available?)
• Information and control: matching channels
• Matching theory
• Matrix versions of the Cauchy and Kantorovich inequalities

Cited in

(3)

• An efficient matching algorithm applied in statistical physics
• scientific article; zbMATH DE number 4016762 (Why is no real title available?)
• A moment-matching Ferguson \& Klass algorithm

This page was built for publication: An algorithm for computing the matching capacity

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