Fungsi carian sedang dalam pembinaan.
Fungsi carian sedang dalam pembinaan.

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 Algoritma Teragih Masa Subquadratik untuk Padanan Maksimum Tepat

Naoki KITAMURA, Taisuke IZUMI

  • pandangan teks lengkap

    0

  • Petikan Ini

Ringkasan:

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.

Jawatankuasa
IEICE TRANSACTIONS on Information Vol.E105-D No.3 pp.634-645
Tarikh penerbitan
2022/03/01
Diumumkan
2021/12/17
ISSN dalam talian
1745-1361
DOI
10.1587/transinf.2021EDP7083
Jenis Manuskrip
PAPER
kategori
Sistem Perisian

Pengarang

Naoki KITAMURA
  Nagoya Institute of Technology
Taisuke IZUMI
  Osaka University

Kata kunci

Contents [show]