A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

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

A Subquadratic-Time Distributed Algorithm for Exact Maximum Matching Um algoritmo distribuído em tempo subquadrático para correspondência máxima exata

Naoki KITAMURA, Taisuke IZUMI

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

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.

Publicação
IEICE TRANSACTIONS on Information Vol.E105-D No.3 pp.634-645
Data de publicação
2022/03/01
Publicitada
2021/12/17
ISSN online
1745-1361
DOI
10.1587/transinf.2021EDP7083
Tipo de Manuscrito
PAPER
Categoria
Sistema de Software

autores

Naoki KITAMURA
  Nagoya Institute of Technology
Taisuke IZUMI
  Osaka University

Palavra-chave