The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Untuk graf G=(V,E), mencari set tepi bercabang yang tidak berkongsi sebarang bucu dipanggil masalah padanan, dan mencari padanan maksimum ialah masalah asas dalam teori algoritma graf teragih. Walaupun algoritma tempatan untuk masalah pemadanan maksimum anggaran telah dikaji secara meluas, algoritma tepat belum banyak dikaji. Malah, tiada algoritma padanan maksimum yang tepat yang lebih pantas daripada sempadan atas yang remeh O(n2) pusingan dikenali untuk keadaan umum. Dalam kertas ini, kami mencadangkan algoritma pusingan $O(s_{max}^{3/2}) rawak dalam model CONGEST, di mana smaks ialah saiz padanan maksimum. Ini ialah algoritma pemadanan maksimum tepat pertama dalam o(n2) pusingan untuk keadaan umum dalam model CONGEST. Bahan teknikal utama hasil kami ialah algoritma teragih untuk mencari laluan tambahan O(smaks) pusingan, yang berdasarkan teknik baru membina a sijil jarang laluan penambahan, yang merupakan subgraf graf input yang mengekalkan sekurang-kurangnya satu laluan penambahan. Untuk mewujudkan pembinaan yang sangat selari bagi sijil jarang, kami juga mencadangkan pencirian baharu bagi sijil jarang, yang mungkin juga mempunyai kepentingan bebas.
Naoki KITAMURA
Nagoya Institute of Technology
Taisuke IZUMI
Osaka University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Salinan
Naoki KITAMURA, Taisuke IZUMI, "A Subquadratic-Time Distributed Algorithm for Exact Maximum Matching" in IEICE TRANSACTIONS on Information,
vol. E105-D, no. 3, pp. 634-645, March 2022, doi: 10.1587/transinf.2021EDP7083.
Abstract: For a graph G=(V,E), finding a set of disjoint edges that do not share any vertices is called a matching problem, and finding the maximum matching is a fundamental problem in the theory of distributed graph algorithms. Although local algorithms for the approximate maximum matching problem have been widely studied, exact algorithms have not been much studied. In fact, no exact maximum matching algorithm that is faster than the trivial upper bound of O(n2) rounds is known for general instances. In this paper, we propose a randomized $O(s_{max}^{3/2})$-round algorithm in the CONGEST model, where smax is the size of maximum matching. This is the first exact maximum matching algorithm in o(n2) rounds for general instances in the CONGEST model. The key technical ingredient of our result is a distributed algorithms of finding an augmenting path in O(smax) rounds, which is based on a novel technique of constructing a sparse certificate of augmenting paths, which is a subgraph of the input graph preserving at least one augmenting path. To establish a highly parallel construction of sparse certificates, we also propose a new characterization of sparse certificates, which might also be of independent interest.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2021EDP7083/_p
Salinan
@ARTICLE{e105-d_3_634,
author={Naoki KITAMURA, Taisuke IZUMI, },
journal={IEICE TRANSACTIONS on Information},
title={A Subquadratic-Time Distributed Algorithm for Exact Maximum Matching},
year={2022},
volume={E105-D},
number={3},
pages={634-645},
abstract={For a graph G=(V,E), finding a set of disjoint edges that do not share any vertices is called a matching problem, and finding the maximum matching is a fundamental problem in the theory of distributed graph algorithms. Although local algorithms for the approximate maximum matching problem have been widely studied, exact algorithms have not been much studied. In fact, no exact maximum matching algorithm that is faster than the trivial upper bound of O(n2) rounds is known for general instances. In this paper, we propose a randomized $O(s_{max}^{3/2})$-round algorithm in the CONGEST model, where smax is the size of maximum matching. This is the first exact maximum matching algorithm in o(n2) rounds for general instances in the CONGEST model. The key technical ingredient of our result is a distributed algorithms of finding an augmenting path in O(smax) rounds, which is based on a novel technique of constructing a sparse certificate of augmenting paths, which is a subgraph of the input graph preserving at least one augmenting path. To establish a highly parallel construction of sparse certificates, we also propose a new characterization of sparse certificates, which might also be of independent interest.},
keywords={},
doi={10.1587/transinf.2021EDP7083},
ISSN={1745-1361},
month={March},}
Salinan
TY - JOUR
TI - A Subquadratic-Time Distributed Algorithm for Exact Maximum Matching
T2 - IEICE TRANSACTIONS on Information
SP - 634
EP - 645
AU - Naoki KITAMURA
AU - Taisuke IZUMI
PY - 2022
DO - 10.1587/transinf.2021EDP7083
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E105-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2022
AB - For a graph G=(V,E), finding a set of disjoint edges that do not share any vertices is called a matching problem, and finding the maximum matching is a fundamental problem in the theory of distributed graph algorithms. Although local algorithms for the approximate maximum matching problem have been widely studied, exact algorithms have not been much studied. In fact, no exact maximum matching algorithm that is faster than the trivial upper bound of O(n2) rounds is known for general instances. In this paper, we propose a randomized $O(s_{max}^{3/2})$-round algorithm in the CONGEST model, where smax is the size of maximum matching. This is the first exact maximum matching algorithm in o(n2) rounds for general instances in the CONGEST model. The key technical ingredient of our result is a distributed algorithms of finding an augmenting path in O(smax) rounds, which is based on a novel technique of constructing a sparse certificate of augmenting paths, which is a subgraph of the input graph preserving at least one augmenting path. To establish a highly parallel construction of sparse certificates, we also propose a new characterization of sparse certificates, which might also be of independent interest.
ER -