Article

Perfect Matching for Biconnected Cubic Graphs in O(n log2n) Time

Authors:

Krzysztof Diks,

Piotr StanczykAuthors Info & Claims

SOFSEM '10: Proceedings of the 36th Conference on Current Trends in Theory and Practice of Computer Science

Pages 321 - 333

https://doi.org/10.1007/978-3-642-11266-9_27

Published: 08 December 2009 Publication History

Abstract

The main result of this paper is a new perfect matching algorithm for biconnected cubic graphs. The algorithm runs in time O ( n log² n ). It is also possible, by applying randomized data structures, to get O ( n log n loglog³ n ) average time. Our solution improves the one given by T. Biedl et al. [3]. The algorithm of Biedl et al. runs in time O ( n log⁴ n ). We use a similar approach. However, thanks to exploring some properties of biconnected cubic graphs we are able to replace complex fully-dynamic biconnectivity data structure with much simpler, dynamic graph connectivity and dynamic tree data structures. Moreover, we present a significant modification of the new algorithm which makes application of a decremental dynamic graph connectivity data structure possible, instead of one supporting the fully dynamic graph connectivity. It gives hope for further improvements.

References

[1]

Alt, H., Blum, N., Mehlhorn, K., Paul, M.: Computing a Maximum Cardinality Matching in a Bipartite Graph in Time O ( n ^1.5 ¿ m /log n ). Information Processing Letters 37, 237-240 (1991)

[2]

Biedl, T.C.: Linear Reductions of Maximum Matching. In: SODA 2001, pp. 825- 826 (2001)

[3]

Biedl, T., Bose, P., Demaine, E., Lubiw, A.: Efficient Algorithms for Petersen's Matching Theorem. Journal of Algorithms 38, 110-134 (2001)

[4]

Frink, O.: A Proof of Petersen's Theorem. The Annals of Mathematics, Series 2 27(4), 491-493 (1926)

[5]

Henzinger, M., King, V.: Fully Dynamic 2-Edge Connectivity Algorithm in Polylogarithmic Time per Operation. Technical Note, Digital Equipment Corp., Systems Research Ctr. (June 12, 1997)

[6]

Holm, J., De Lichtenserg, K., Thorup, M.: Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge and Biconnectivity. Journal of the ACM (JACM) 48, 723-760 (2001)

[7]

Lovasz, L., Plummer, M. D.: Matching Theory. North-Holland Publishing Co., Amsterdam (1986)

[8]

Micali, S., Vazirani, V. V.: An O (¿ nm ) Algorithm for Finding Maximum Matching in General Graphs. In: Proceedings of FOCS 1980, pp. 17-27. IEEE, Los Alamitos (1980)

[9]

Petersen, J.: Die Theorie der regulären Graphs. Acta Mathematica 15, 193-220 (1891)

[10]

Karpinski, M., Rytter, W.: Fast Parallel Algorithms for Graph Matching Problem. Oxford University Press, Oxford (1998)

[11]

Schrijver, A.: Combinatorial Optimization - Polyhedra and Efficiency. Parts II and III. Springer, Berlin (2003)

[12]

Schrijver, A.: Bipartite Edge Coloring in O (¿m) Time. SIAM Journal on Computing 28(3), 841-846 (1999)

[13]

Sleator, D. D., Tarjan, R. E.: A Data Structure for Dynamic Trees. In: Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing, pp. 114-122 (1981)

[14]

Tarjan, R. E.: Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (1983)

[15]

Thorup, M.: Near-Optimal Fully-Dynamic Graph Connectivity. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pp. 343-350 (2000)

[16]

Thorup, M.: Decremental Dynamic Connectivity. In: Proceedings of the 8th ACM Symposium on Discrete Algorithms (SODA), pp. 305-313 (1997)

[17]

Mucha, M.: Finding Maximum Matchings via Gaussian Elimination. PhD Thesis, Warsaw University, Faculty of Mathematics, Informatics and Mechanics

[18]

Harvey, N. J. A.: Algebraic Algorithms for Matching and Matroid Problems. Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology

[19]

Greenlaw, R., Petreschi, R.: Cubic Graphs. ACM Computing Surveys (CSUR) 27(4), 471-495 (1995)

Cited By

Ghanbari BŠámal R(2024)Approximate Cycle Double CoverCombinatorial Algorithms10.1007/978-3-031-63021-7_32(421-432)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-63021-7_32
Evans WRzążewski PSaeedi NShin CWolff A(2019)Representing Graphs and Hypergraphs by Touching Polygons in 3DGraph Drawing and Network Visualization10.1007/978-3-030-35802-0_2(18-32)Online publication date: 17-Sep-2019
https://dl.acm.org/doi/10.1007/978-3-030-35802-0_2
Holm JRotenberg EThorup MCzumaj A(2018)Dynamic bridge-finding in õ(log2 n) amortized timeProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175269(35-52)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175269
Show More Cited By

Perfect Matching for Biconnected Cubic Graphs in O(n log2n) Time
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation

Recommendations

Location-domination and matching in cubic graphs

A dominating set of a graph G is a set D of vertices of G such that every vertex outside D is adjacent to a vertex in D . A locating-dominating set of G is a dominating set D of G with the additional property that every two distinct vertices outside D ...
Matching transformation graphs of cubic bipartite plane graphs

In this paper, we explore some properties of the matching transformation graph of a connected cubic bipartite plane graph G. We prove that if M is any perfect matching of G, then G has at least two disjoint M-alternating faces. This result is sharp in ...
Split-Perfect Graphs: Characterizations and Algorithmic Use

Two graphs G and H with the same vertex set V are P₄-isomorphic if every four vertices {a,b,c,d} \subseteq V$ induce a chordless path (denoted by P₄) in G if and only if they induce a P₄ in H. We call a graph split-perfect if it is P₄-isomorphic to a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

SOFSEM '10: Proceedings of the 36th Conference on Current Trends in Theory and Practice of Computer Science

December 2009

778 pages

ISBN:9783642112652

Editors:
Jan Leeuwen
Department of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands 3584 CH
,
Anca Muscholl
LaBRI, Universit Bordeaux, Talence Cedex, France 1F-33405
,
David Peleg
Department of Computer Science & Applied Mathematics, Weizmann Institute, Faculty of Mathematics and Computer Science, Rehovot, Israel 76100
,
Jaroslav Pokorný
Department of Software Engineering Faculty of Mathematics and Physics Malostranské nám, Charles University, Prague 1, Czech Republic 25 11800
,
Bernhard Rumpe
Software Engineering, Department of Computer Science, RWTH Aachen University, Aachen, Germany D-52074

Copyright © Springer-Verlag Berlin Heidelberg.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 08 December 2009

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ghanbari BŠámal R(2024)Approximate Cycle Double CoverCombinatorial Algorithms10.1007/978-3-031-63021-7_32(421-432)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-63021-7_32
Evans WRzążewski PSaeedi NShin CWolff A(2019)Representing Graphs and Hypergraphs by Touching Polygons in 3DGraph Drawing and Network Visualization10.1007/978-3-030-35802-0_2(18-32)Online publication date: 17-Sep-2019
https://dl.acm.org/doi/10.1007/978-3-030-35802-0_2
Holm JRotenberg EThorup MCzumaj A(2018)Dynamic bridge-finding in õ(log2 n) amortized timeProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175269(35-52)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175269
(2016)The cost of perfection for matchings in graphsDiscrete Applied Mathematics10.1016/j.dam.2014.12.006210:C(112-122)Online publication date: 10-Sep-2016
https://dl.acm.org/doi/10.1016/j.dam.2014.12.006
Babenko MUrbanovich T(2011)Linear algorithm for selecting an almost regular spanning subgraph in an almost regular graphProblems of Information Transmission10.1134/S003294601103005747:3(269-273)Online publication date: 1-Sep-2011
https://dl.acm.org/doi/10.1134/S0032946011030057

View Options

View options

Figures

Tables

Media

View Table of Conten