Graph Golf

Publications

Update 2023-01-09

Here is a list of publications, presentations and softwares related to Graph Golf. Some are in Japanese.

Academic Papers and Conference Proceedings

• Dual Diagonal Mesh: An Optimal Memory Cube Network Under Geometric Constraints
  Masashi Oda, Kai Keida and Ryota Yasudo
  Eleventh International Symposium on Computing and Networking (CANDAR), Nov. 2023
• Optimization Algorithm with Automatic Adjustment of the Number of Switches in the Order/Radix Problem
  Masaki TSUKAMOTO, Yoshiko HANADA, Masahiro NAKAO, Keiji YAMAMOTO
  IEICE Transactions on Information and Systems, Volume E106.D Issue 12 Pages 1979-1987, Dec. 2023
• 遺伝的アルゴリズムによるOrder/Degree問題におけるグリッドグラフの一解法
  木村弘登，花田良子，中尾昌広，山本啓二
  信学技報, vol. 123, no. 293, CPSY2023-32, pp. 31-35, 2023年12月.
• Graph optimization algorithm using symmetry and host bias for low-latency indirect network
  Masahiro Nakao, Masaki Tsukamoto, Yoshiko Hanada, Keiji Yamamoto
  Parallel Computing, Available online, 19 Oct. 2022, 102983 (14 pages)
• Order/Radix Problemにおけるスイッチ数自動調整機能を持つ最適化アルゴリズムの提案
  塚本雅生, 花田良子, 中尾昌広, 山本啓二
  第27回計算工学講演会[C-05-01]
• Order/Radix Problemにおける対称性とホストの偏りを利用した最適化アルゴリズムの提案
  中尾昌広, 塚本雅生, 花田良子, 山本啓二
  情報処理学会研究報告(第182回HPC研究会)，14ページ, Dec 2021
• Graph optimization algorithm for low-latency interconnection networks
  Masahiro Nakao, Maaki Sakai, Yoshiko Hanada, Hitoshi Murai, Mitsuhisa Sato
  Parallel Computing, Available online 1 July 2021, 102805 (12 pages)
• 最適化アルゴリズムによる低遅延相互結合網のためのグラフ構成法
  中尾 昌広, 酒井 真章, 花田 良子, 村井 均, 佐藤 三久
  情報処理学会研究報告(第173回HPC研究会)，11ページ, Mar 2020
• Parallelization of All-Pairs-Shortest-Path Algorithms in Unweighted Graph
  Masahiro Nakao, Hitoshi Murai, Mitsuhisa Sato
  Proceedings of the International Conference on High Performance Computing in Asia-Pacific Region (HPC Asia 2020), pp.63-72, 2020
• The Degree Diameter Problem for Host-Switch Graphs
  Ryota. Yasudo and Koji Nakano
  Seventh International Symposium on Computing and Networking Workshops (CANDARW), pp.249-255, 2019
• Designing High-Performance Interconnection Networks with Host-Switch Graphs
  Ryota Yasudo, Michihiro Koibuchi, Koji Nakano, Hiroki Matsutani and Hideharu Amano
  IEEE Transactions on Parallel and Distributed Systems, vol. 30, no. 2, pp. 315-330, Feb. 2019
• Efficient GPU Implementations to Compute the Diameter of a Graph
  Daisuke Takafuji, Koji Nakano, Yasuaki Ito
  Proceedings of the 7th International Symposium on Computing and Networking (CANDAR'19), pp.102-111, 2019
• A Method for Order/Degree Problem Based on Graph Symmetry and Simulated Annealing with MPI/OpenMP Parallelization
  Masahiro Nakao, Hitoshi Murai, Mitsuhisa Sato
  Proceedings of the International Conference on High Performance Computing in Asia-Pacific Region (HPC Asia 2019), pp.128–137, 2019.
• Order/Degree問題のための重みなしグラフにおける全点対間最短経路アルゴリズムの並列化
  中尾昌広, 村井均, 佐藤三久
  情報処理学会研究報告ハイパフォーマンスコンピューティング (HPC), vol.2019-HPC-171, no.10, pp.1–10, 2019.
• 小直径グラフ探索コンペ "Graph Golf" 5年間の成果
  藤原一毅, 中野浩嗣, 鯉渕道紘
  情報処理学会研究報告システム・アーキテクチャ (ARC), vol.2019-ARC-237, no.21, pp.1–9, 2019.
• 大規模Order/Degree問題に対する最適化アルゴリズムの並列化と解探索性能の評価
  中尾昌広, 村井均, 佐藤三久
  計算工学講演会論文集, vol.24, 6 pages, 2019.
• Solving Order/Degree Problems by Using EDA-GK with a Novel Sampling Method
  Ryoichi Hasegawa, Hisashi Handa
  Journal of Advanced Computational Intelligence and Intelligent Informatics, vol.22, no.2, pp.236–241, 2018.
• Order Adjustment Approach Using Cayley Graphs for the Order/Degree Problem
  Teruaki Kitasuka, Takayuki Matsuzaki, Masahiro Iida
  IEICE Transactions on Information and Systems, vol.E101.D, no.12, pp.2908–2915, 2018.
• The Diameter of Dense Random Regular Graphs
  Nobutaka Shimizu
  Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.1934–1944, 2018.
• Some Torus-embedded Graphs with Regular Structure Have the Minimum Diameter and the Minimum Average Shortest Path Length
  Noriyuki Fujimoto, Hiroyuki Kobayashi
  Proceedings of the 2018 IEEE Region 10 Conference (TENCON 2018), pp.2264–2269, 2018.
• MPI/OpenMP並列によるグラフ対称性とSimulated Annealingを用いたOrder/Degree問題の一解法
  中尾昌広, 村井均, 佐藤三久
  情報処理学会研究報告ハイパフォーマンスコンピューティング (HPC), vol.2018-HPC-167, no.23, pp.1–11, 2018.
• Solving order/degree problems by using EDA-GK
  Hisashi Handa, Ryoichi Hasegawa
  Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO '17), pp.25–26, 2017.
• Towards Ideal Hop Counts in Interconnection Networks with Arbitrary Size
  Michihiro Koibuchi, Ikki Fujiwara, Fabien Chaix, Henri Casanova
  Proceedings of the 4th International Symposium on Computing and Networking (CANDAR'16), pp.188–194, 2016.
• Constructing large-scale low-latency network from small optimal networks
  Ryosuke Mizuno, Yawara Ishida
  Proceedings of the Tenth IEEE/ACM International Symposium on Networks-on-Chip (NOCS 2016), 6 pages, 2016.
• A heuristic method of generating diameter 3 graphs for order/degree problem
  Teruaki Kitasuka, Masahiro Iida
  Proceedings of the Tenth IEEE/ACM International Symposium on Networks-on-Chip (NOCS 2016), 6 pages, 2016.
• Average shortest path length of graphs of diameter 3
  Nobutaka Shimizu, Ryuhei Mori
  Proceedings of the Tenth IEEE/ACM International Symposium on Networks-on-Chip (NOCS 2016), 6 pages, 2016.
• Randomly Optimized Grid Graph for Low-Latency Interconnection Networks
  Koji Nakano, Daisuke Takafuji, Satoshi Fujita, Hiroki Matsutani, Ikki Fujiwara, Michihiro Koibuchi
  Proceedings of the 45th International Conference on Parallel Processing (ICPP 2016), pp.340–349, 2016.
• Deterministic Construction of Regular Geometric Graphs with Short Average Distance and Limited Edge Length
  Satoshi Fujita, Koji Nakano, Michihiro Koibuchi, Ikki Fujiwara
  Proceedings of the International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP 2016), pp.295–309, 2016.
• Average Shortest Path Length of Graphs of Diameter 3
  Nobutaka Shimizu, Ryuhei Mori
  arXiv:1606.05119, 2016.
• A Heuristic Method of Generating Diameter 3 Graphs for Order/Degree Problem
  Teruaki Kitasuka, Masahiro Iida
  arXiv:1609.03136, 2016.
• トーラスに規則的に辺を追加した直径および平均パス長最小のグラフ
  小林寛之, 藤本典幸
  情報処理学会研究報告システム・アーキテクチャ (ARC), vol.2016-ARC-221, no.45, pp.1–6, 2016.
• みんなでOrder/Degree 問題を解いて究極の低遅延相互結合網をつくろう
  藤原一毅, 藤田聡, 中野浩嗣, 井上武, 鯉渕道紘
  情報処理学会研究報告システム・アーキテクチャ (ARC), vol.2015-ARC-216, no.34, pp.1–6, 2015.

Workshop Presentations

• A Method for Order/Degree Problem Based on Graph Symmetry and Simulated Annealing
  Masahiro Nakao
  Invited talk in the Graph Golf workshop in CANDAR'18, 2018.
• Simulated annealing for Graph Golf
  Toru Koizumi
  Invited talk in the Graph Golf workshop in CANDAR'18, 2018.
• Search voltage graph for order degree problem
  Masato Haruishi
  Invited talk in the Graph Golf workshop in CANDAR'18, 2018.
• ASPL Optimization ApproachUsing Brown and Cayley Graphs
  Takayuki Matsuzaki, Teruaki Kitasuka, Masahiro Iida
  Invited talk in the Graph Golf workshop in CANDAR'17, 2017.
• Approximate evaluation and voltage assignment for order/degree problem
  Ibuki Kawamata
  Invited talk in the Graph Golf workshop in CANDAR'17, 2017.
• Making smallest-diameter graphs at "Graph Golf"
  Takayuki Matsuzaki, Teruaki Kitasuka, Masahiro Iida
  Invited talk in the Graph Golf workshop in CANDAR'16, 2016.
• Small ASPL Regular Graphs of Order=2²ⁿ Degree=2ⁿ
  Yawara Ishida, Ryosuke Mizuno
  Invited talk in the Graph Golf workshop in CANDAR'16, 2016.
• 既知のグラフを用いた小直径グラフの構成
  水野良祐, 石田やわら
  第15回情報科学技術フォーラム (FIT 2016), 2016.
• グラフゴルフのはじめ方 - 手書きグラフから経験的手法によるグラフ生成まで
  北須賀輝明, 飯田全広
  第15回情報科学技術フォーラム (FIT 2016), 2016.
• 直径3のグラフにおける平均最短経路長の近似
  清水伸高, 森立平
  第15回情報科学技術フォーラム (FIT 2016), 2016.
• Constructing large-scale low-latency network from small optimal networks
  Ryosuke Mizuno, Yawara Ishida
  The Tenth IEEE/ACM International Symposium on Networks-on-Chip (NOCS 2016), 2016.
• A heuristic method of generating diameter 3 graphs for order/degree problem
  Teruaki Kitasuka, Masahiro Iida
  The Tenth IEEE/ACM International Symposium on Networks-on-Chip (NOCS 2016), 2016.
• Average shortest path length of graphs of diameter 3
  Nobutaka Shimizu, Ryuhei Mori
  The Tenth IEEE/ACM International Symposium on Networks-on-Chip (NOCS 2016), 2016.
• ASPL-approximation for graph of diameter 3
  Nobutaka Shimizu, Ryo Ashida, Ryuhei Mori
  Invited talk in the Graph Golf workshop in CANDAR'15, 2015.
• The construction of a regular graph
  Ryosuke Mizuno, Yawara Ishida
  Invited talk in the Graph Golf workshop in CANDAR'15, 2015.
• Our Experience of Graph Golf Competition
  Teruaki Kitasuka, Masahiro Iida
  Invited talk in the Graph Golf workshop in CANDAR'15, 2015.

Softwares

• ORP library, including a graphical tool, for order/radix problem Calculates h-ASPL
  Masahiro Nakao
• graph_ASPL Computation of average shortest path length (ASPL) of a graph
  Ryuhei Mori
• APSP Solves APSP (All Pairs Shortest Paths) of a noweight undirected graph
  Masahiro Nakao
• lower-lattice.pl Calculates the tighter lower bound of diameter and ASPL of a grid graph
  Koji Nakano, Daisuke Takafuji
• host-switch-aspl Calculates h-diameter and h-ASPL of a given host-switch graph
  Ryota Yasudo
• host-switch-random Generates a random host-switch graph and calculates the lower bounds for given n and r
  Ryota Yasudo
• apsp_sparse_gpu computes APSP (All Pairs Shortest Paths) of low-degree unweighted regular graphs. It is based on graph_ASPL
  Ryuta Kawano