大域的分散グラフアルゴリズムに対するパラメタライズド手法の確立

全局分布图算法参数化方法的建立

• 批准号: 19K11824
• 负责人: 泉 泰介
• 金额: $ 2.83万
• 依托单位: Osaka University (2020-2022)Nagoya Institute of Technology (2019)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2019
• 资助国家: 日本
• 起止时间: 2019-04-01 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-19K11824/
• 关键词: 分散アルゴリズム; グラフアルゴリズム; 計算複雑性; 固定パラメタ容易性; 固定パラメタアルゴリズム; グラフ理論; 組み合わせ最適化

複数の計算機が通信リンクで相互接続した分散システムにおいて、ネットワークのトポロジカルな構造に立脚した何らかの組み合わせ最適化問題(最短経路問題、彩色問題等)をネットワーク自身が計算したいという要求は自然な問題設定であり、また多くの応用が存在する。分散グラフアルゴリズムとは、複数の計算機が通信リンクで相互接続した分散システムにおいて、ネットワークのトポロジカルな構造を入力データと見なしてグラフアルゴリズムを実行する枠組みである。本研究では、グラフ理論の基本的な諸問題のうち、特に求解のために大域的な情報収集を必要とする問題(大域的な問題)を対象とし、入力インスタンスの困難性に応じた最適な計算時間を達成する分散グラフアルゴリズムをパラメタライズドアルゴリズムの文脈から模索し，以下に示すような成果を得た．令和4年度に関しては，主に既に得られていた知見を研究論文として刊行する，ならびに採択が決定した論文を国際会議にて発表することが主な作業であったが，昨年度に得られていた以下の2成果についてそれぞれ国際会議における発表，論文刊行を行った．(1)木幅制限グラフに対する効率的な分散グラフアルゴリズムの統一的設計手法の提案(2)最大マッチング問題に対する高速なパラメタライズド分散アルゴリズムの発見また，本研究に関連する以下の追加的な成果を得ることができた．(3)最短経路の最致命辺問題に対するパラメータ可複雑性の精緻な解析

Multiple computers communicate with each other in a decentralized manner, creating a network structure, and combining optimization problems (shortest path problems, color problems, etc.). Decentralized communication between multiple computers is a way to communicate with one another. Decentralized communication between multiple computers is a way to integrate multiple computers into one another. This study is aimed at solving the basic problems of large-domain information set problems (large-domain problems), and the difficulty of calculating the optimal time to achieve them. The results are shown below. In the fourth year of the year, the main research paper was published, and the main research paper was published. The main research paper was published in the international conference. The main research paper was published in the international conference. The following two achievements were obtained in the last year. The main research paper was published in the international conference. (1)A unified design method for the dispersion of wood amplitude control efficiency is proposed.(2) The maximum amplitude control problem is the high speed dispersion of wood amplitude control efficiency. The following additional results are obtained. (3)A refined analysis of the repeatability of the shortest path and the deadliest path problem

项目成果

k-極大独立集合検証問題の分散計算複雑性

k-最大独立集验证问题的分布式计算复杂度

• 发表时间: 2021
• 作者: 北村 直暉;泉 泰介;佐藤 僚祐
• 通讯作者: 佐藤 僚祐

Brief Announcement: Message Reduction in the LOCAL Model is a Free Lunch.

简短声明：LOCAL 模型中的消息缩减是免费午餐。

• DOI: 10.1145/3293611.3331582
• 发表时间: 2019
• 期刊: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019.
• 作者: Ryota Eguchi;Naoki Kitamura;Taisuke Izumi;Taisuke Izumi,Francois Le Gall,Frederic Magniez;Yuval Emek,Noga Harlev,Taisuke Izumi;Yuichi Sudo,Fukuhito Ooshita,Taisuke Izumi,Hirotsugu Kakugawa,Toshimitsu Masuzawa;Taisuke Izumi,Francois Le Gall;Shimon Bitton,Yuval Emek,Taisuke Izumi,Shay Kutten
• 通讯作者: Shimon Bitton,Yuval Emek,Taisuke Izumi,Shay Kutten

CONGEST モデルにおける最大マッチングのための劣二乗アルゴリズム

CONGEST 模型中最大匹配的 Subsquares 算法

• 发表时间: 2021
• 作者: 北村 直暉;泉 泰介
• 通讯作者: 泉 泰介

Sublinear-Space Lexicographic Depth-First Search for Bounded Treewidth Graphs and Planar Graphs

有界树宽图和平面图的次线性空间词典深度优先搜索

• 发表时间: 2020
• 期刊: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
• 作者: Taisuke Izumi;Yota Otachi
• 通讯作者: Yota Otachi

Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model.

CONGEST 模型中三角形查找的量子分布式算法。

• 发表时间: 2020
• 期刊: 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
• 作者: Ryota Eguchi;Naoki Kitamura;Taisuke Izumi;Taisuke Izumi,Francois Le Gall,Frederic Magniez
• 通讯作者: Taisuke Izumi,Francois Le Gall,Frederic Magniez