Efficient recognition of equimatchable graphs. (English) Zbl 1329.05243
Summary: In this paper, we give a new characterization of equimatchable graphs that are graphs with all maximal matchings having the same size. This gives an \(O(n^2m)\)-algorithm for deciding whether a general graph of order \(n\) and with \(m\) edges is equimatchable. An \(O(n^{4.5})\) recognition algorithm based on the Gallai-Edmonds decomposition already follows from [M. Lesk et al., in: Graph theory and combinatorics, Proc. Conf. Hon. P. Erdős, Cambridge 1983, 239–254 (1984; Zbl 0548.05048)]. Our characterization and algorithm use only some basic knowledge on matchings and can be formulated in a simplier way. Moreover it leads to a better time complexity.
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
Citations:
Zbl 0548.05048References:
| [1] | Berge, C., Graphs and Hypergraphs (1973), North-Holland Publishing Company: North-Holland Publishing Company Amsterdam · Zbl 0483.05029 |
| [2] | Edmonds, J., Paths, trees and flowers, Can. J. Math., 17, 449-467 (1965) · Zbl 0132.20903 |
| [3] | Favaron, O., Equimatchable factor-critical graphs, J. Graph Theory, 4, 439-448 (1986) · Zbl 0614.05028 |
| [4] | Frendrup, A.; Hartnell, B.; Preben, D., A note on equimatchable graphs, Australas. J. Comb., 46, 185-190 (2010) · Zbl 1196.05076 |
| [5] | Kameda, T.; Munro, I., An \(O(| V | . | E |)\) algorithm for maximum matching in general graphs, Computing, 12, 91-98 (1974) · Zbl 0278.65069 |
| [6] | Kawarabayashi, K.-I.; Plummer, M. D., Bounding the size of equimatchable graphs of fixed genus, Graphs Comb., 1, 91-99 (2009) · Zbl 1191.05033 |
| [7] | Kawarabayashi, K.-I.; Plummer, M. D.; Saito, A., On two equimatchable graph classes, The 18th British Combinatorial Conference. The 18th British Combinatorial Conference, Brighton, 2001. The 18th British Combinatorial Conference. The 18th British Combinatorial Conference, Brighton, 2001, Discrete Math., 1, 3, 263-274 (2003) · Zbl 1022.05065 |
| [8] | Lesk, M.; Plummer, M. D.; Pulleyblank, W. R., Equi-matchable graphs, (Graph Theory and Combinatorics. Graph Theory and Combinatorics, Cambridge, 1983 (1984), Academic Press: Academic Press London) · Zbl 0548.05048 |
| [9] | Lewin, M., Matching-perfect and cover-perfect graphs, Isr. J. Math., 18, 345-347 (1974) · Zbl 0298.05137 |
| [10] | Lovász, L.; Plummer, M. D., Matching Theory, Annals of Discrete Mathematics, vol. 29 (1986), North-Holland: North-Holland Amsterdam · Zbl 0618.05001 |
| [11] | Meng, D. H.-C., Matchings and coverings for graphs (1974), Michigan State University: Michigan State University East Lansing, MI, PhD thesis |
| [12] | Micali, S.; Vazirani, V., An \(O(\sqrt{| V |} | E |)\) algorithm for finding maximum matching in general graphs, (Proceedings of 21st Annual Symposium on Foundations of Computer Science, FOCS 1980, IEEE (1980)), 17-27 |
| [13] | Sumner, D. P., Randomly matchable graphs, J. Graph Theory, 3, 183-186 (1979) · Zbl 0404.05053 |
| [14] | Tankus, D.; Tarsi, M., The structure of well-covered graphs and the complexity of their recognition problems, J. Comb. Theory, Ser. B, 67, 230-233 (1997) · Zbl 0873.05074 |
| [15] | Stauffer, G.; Faenza, Y.; Oriolo, G., An algorithmic decomposition of claw-free graphs leading to an \(O(n^3)\)-algorithm for the weighted stable set problem, (Randall, D., Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA (2011)), 630-646 · Zbl 1376.05148 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
