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
Para um gráfico G=(V,E), encontrar um conjunto de arestas disjuntas que não compartilham nenhum vértice é chamado de problema de correspondência, e encontrar a correspondência máxima é um problema fundamental na teoria dos algoritmos de grafos distribuídos. Embora algoritmos locais para o problema de correspondência máxima aproximada tenham sido amplamente estudados, algoritmos exatos não foram muito estudados. Na verdade, nenhum algoritmo de correspondência máxima exata que seja mais rápido que o limite superior trivial de O(n2) rodadas são conhecidas para instâncias gerais. Neste artigo, propomos um algoritmo $O(s_{max}^{3/2})$-round aleatório no modelo CONGEST, onde smax é o tamanho da correspondência máxima. Este é o primeiro algoritmo de correspondência máxima exata em o(n2) rodadas para instâncias gerais no modelo CONGEST. O principal ingrediente técnico do nosso resultado é um algoritmo distribuído para encontrar um caminho crescente em O(smax) rodadas, que se baseia em uma nova técnica de construção de um certificado esparso de caminhos aumentados, que é um subgrafo do gráfico de entrada preservando pelo menos um caminho aumentado. Para estabelecer uma construção altamente paralela de certificados esparsos, propomos também uma nova caracterização de certificados esparsos, que também pode ser de interesse independente.
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.
Copiar
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
Copiar
@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},}
Copiar
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 -