金沢大学 > 理工学域 > 電子情報通信学類
金沢大学 > 自然科学研究科 > 博士前期課程 > 電子情報学専攻
金沢大学 > 自然科学研究科 > 博士後期課程 > 電子情報科学専攻
English    
イラスト イラスト

NPCL -Matsubayashi Lab.-

-Networks and Parallel Computation Laboratory-

  Top > Publications

■ Publications

2023

  • Akira Matsubayashi and Yushi Saito, A Faster Algorithm for Recognizing Directed Graphs Invulnerable to Braess's Paradox, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023), Open Access Series in Informatics (OASIcs), vol. 115, pp. 12:1-12:19, 2023. DOI:10.4230/OASIcs.ATMOS.2023.12. [Best Paper Award]
  • Yu-Ting Wang, Meng-Hsun Tsai, and Akira Matsubayashi, Reducing Redundant Transmissions for Message Broadcast in Vehicular Ad-Hoc Networks, 2023 IEEE 20th Annual Consumer Communications & Networking Conference (CCNC), pp. 969-970, 2023. DOI:10.1109/CCNC51644.2023.10060804.

2022

  • 斎藤 優至,松林 昭, Braessパラドックスが起こり得ない有向グラフの多項式時間判定アルゴリズム, 情報処理学会 第84回全国大会講演論文集(1), pp. 243-244, March 2022.
  • 二瓶 勢真,松林 昭, k+1点上のk-ページ移動問題に対する漸近的に最適なオンラインアルゴリズム, 情報処理学会 第84回全国大会講演論文集(1), pp. 223-224, March 2022.

2021

  • Akira Matsubayashi, Non-Greedy Online Steiner Trees on Outerplanar Graphs, Algorithmica, vol. 83, no. 2, pp. 613-640, February 2021. (published online 16 October 2020). DOI:10.1007/s00453-020-00768-6. Preliminary version appeared in WAOA 2016 (LNCS 10138).

2020

  • Akira Matsubayashi, A 3+Omega(1) Lower Bound for Page Migration, Algorithmica, vol. 82, no. 9, pp. 2535-2563, September 2020. (published online 23 March 2020). DOI:10.1007/s00453-020-00696-5. Preliminary version appeared in CANDAR 2015.
  • Akira Matsubayashi, Better Embedding of k-Outerplanar Graphs into Random Trees, 情報処理学会研究報告, vol. 2020-AL-177, no. 4, pp. 1-8, March 2020.

2018

  • Akira Matsubayashi, An Improved Algorithm for Uniform Page Migration on Euclidean Space, 情報処理学会研究報告, vol. 2018-AL-170, no. 2, pp. 1-5, November 2018.

2017

  • Akira Matsubayashi, Non-greedy Online Steiner Trees on Outerplanar Graphs, Proceedings of the 14th Workshop on Approximation and Online Algorithms (WAOA 2016), Lecture Notes in Computer Science, vol. 10138, pp. 129-141, 2017. DOI:10.1007/978-3-319-51741-4_11.

2016

  • Amanj Khorramian and Akira Matsubayashi, Uniform Page Migration Problem in Euclidean Space, Algorithms, vol. 9, no. 3, 57:1-7, August 2016. DOI:10.3390/a9030057. (manuscript)

2015

  • Akira Matsubayashi, Bounding Dilation and Edge-Congestion of Separator-Based Graph Embeddings into Grids, Proceedings of the 3rd International Symposium on Computing and Networking (CANDAR 2015), pp. 321-327, 2015. DOI:10.1109/CANDAR.2015.59. [presented at 7th International Workshop on Parallel and Distributed Algorithms and Applications and selected as Best Paper]
  • Akira Matsubayashi, A 3+Omega(1) Lower Bound for Page Migration, Proceedings of the 3rd International Symposium on Computing and Networking (CANDAR 2015), pp. 314-320, 2015. DOI:10.1109/CANDAR.2015.62.
  • Akira Matsubayashi, Better Online Steiner Trees on Outerplanar Graphs, 情報処理学会研究報告, vol. 2015-AL-155, no. 2, pp. 1-5, November 2015.
  • Akira Matsubayashi, A 3+Omega(1) Lower Bound for Page Migration, 電子情報通信学会技術研究報告, vol. 115, no. 84, (COMP2015-7), pp. 29-36, June 2015.
  • Akira Matsubayashi, Separator-Based Graph Embedding into Multidimensional Grids with Small Edge-Congestion, Discrete Applied Mathematics, vol. 185, pp. 119-137, April 2015 (published online 12 December 2014). DOI:10.1016/j.dam.2014.11.024. (manuscript)
  • Akira Matsubayashi, Asymptotically Optimal Online Page Migration on Three Points, Algorithmica, vol. 71, no. 4, pp. 1035-1064, April 2015 (published online 17 October 2013). DOI:10.1007/s00453-013-9841-9. (manuscript). Preliminary version appeared in WAOA 2012 (LNCS 7846).

2014

  • Akira Matsubayashi, Online Steiner Trees on Outerplanar Graphs, 情報処理学会研究報告, vol. 2014-AL-150, no. 8, pp. 1-4, November 2014.

2013

  • Akira Matsubayashi, Bounding Dilation of Separator-Based Graph Embeddings into Grids, 情報処理学会研究報告, vol. 2013-AL-145, no. 18, pp. 1-8, November 2013.

2012

  • 光地 洋平,松林 昭, 二次元三角格子型無線ネットワークにおける電力最小ブロードキャストの下界, 電子情報通信学会技術研究報告, vol. 112, no. 340, (COMP2012-48), pp. 27-31, December 2012.
  • 林 克幸,松林 昭, 定数コストの横断辺を持つ梯子状ネットワークの最適化, 情報処理学会研究報告, vol. 2012-AL-142, no. 6, pp. 1-5, October. 2012.
  • Akira Matsubayashi, Asymptotically Optimal Online Page Migration on Three Points, Proceedings of the 10th Workshop on Approximation and Online Algorithms (WAOA 2012), Lecture Notes in Computer Science, vol. 7846, pp. 107-119, 2013.

2011

  • Akira Matsubayashi, Optimal Online Page Migration on Three Points, 情報処理学会研究報告, vol. 2011-AL-137, no. 8, pp. 1-8, November. 2011.
  • 光地 洋平,松林 昭, 二次元三角格子型無線ネットワークにおける電力最小ブロードキャスト, 電子情報通信学会技術研究報告, vol. 111, no. 293, (CAS2011-81), pp. 101-106, November 2011.
  • Atsushi Murata and Akira Matsubayashi, Minimum Energy Broadcast on Rectangular Grid Wireless Networks, Theoretical Computer Science, vol. 421, no. 39, pp. 5167-5175, September 2011. DOI:10.1016/j.tcs.2011.05.024. (manuscript). Preliminary version appeared in ALGOSENSORS 2010 (LNCS 6451).

2010

  • Atsushi Murata and Akira Matsubayashi, Minimum Energy Broadcast on Rectangular Grid Wireless Networks, Proceedings of the 6th International Workshop on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS 2010), Lecture Notes in Computer Science, vol. 6451, pp. 34-46, 2010.
  • Atsushi Murata and Akira Matsubayashi, Minimum Energy Broadcast on Rectangular Grid Wireless Networks, 電子情報通信学会技術研究報告, vol. 110, no. 104, (COMP2010-20), pp. 29-35, June 2010.

2009

  • Yasuyuki Kawamura and Akira Matsubayashi, Randomized Online File Allocation on Uniform Cactus Graphs, IEICE Transactions on Information and Systems, vol. E92-D, no. 12, pp. 2416-2421, December 2009. DOI:10.1587/transinf.E92.D.2416. (manuscript). Preliminary version appeared in ISPDC 2008.
  • Akira Matsubayashi, Separator-Based Graph Embedding into Higher-Dimensional Grids with Small Congestion, Proceedings of the 2009 IEEE International Symposium on Circuits and Systems (ISCAS 2009), pp. 2938-2941, May 2009. (manuscript)

2008

  • Akira Matsubayashi, Separator-Based Graph Embedding into Higher-Dimensional Grids with Small Congestion, 電子情報通信学会技術研究報告, vol. 108, no. 277, (CAS2008-47), pp. 11-16, November 2008.
  • Akira Matsubayashi, New Bounds for Online Page Migration on Three Points, 情報処理学会研究報告, vol. 2008, no. 108, pp. 49-56, November 2008.
  • Yasuyuki Kawamura and Akira Matsubayashi, Randomized Online File Allocation on Uniform Ring Networks, Proceedings of the 7th International Symposium on Parallel and Distributed Computing (ISPDC 2008), pp. 449-453, July 2008.
  • Akira Matsubayashi, Uniform Page Migration on General Networks, International Journal of Pure and Applied Mathematics, vol. 42, no. 2, pp. 161-168, 2008. (info) (full text)

2007

  • 川村 泰之,小林 正雄,松林 昭, リングネットワークにおけるファイル配置問題について, 情報処理学会研究報告, vol. 2007, no. 119, pp. 41-47, November 2007.
  • 片山 真喜, 松林 昭, 3点ネットワークにおける競合的オンラインデータ移動アルゴリズム, 電気関係学会北陸支部連合大会講演論文集, E-46, September 2007.
  • Akira Matsubayashi, Page Migration on Ring Networks, Fourth International Conference of Applied Mathematics and Computing, vol. 5, p. 369, August 2007.

2006

  • Akira Matsubayashi, Page Migration on Ring Networks, 情報処理学会研究報告, vol. 2006, no. 122, pp. 35-42, November 2006. (manuscript)
  • Akira Matsubayashi, Separator-Based Graph Embedding into Higher Dimensional Grids with Small Edge-Congestion, 2006ソサイエティ大会講演論文集, AS-1-5, September 2006.
  • Hiroaki Takai, Takashi Kanatani, and Akira Matsubayashi, Path Coloring on Binary Caterpillars, IEICE Transactions on Information and Systems, vol. E89-D, no. 6, pp. 1906-1913, June 2006. DOI:10.1093/ietisy/e89-d.6.1906. (manuscript)

2005

  • Akira Matsubayashi, Small Congestion Embedding of Separable Graphs into Grids of the Same Size, Proceedings of the 2005 IEEE International Symposium on Circuits and Systems (ISCAS 2005), pp. 1354-1357, May 2005.
  • 高井 洋明,松林 昭, 2-パス光ネットワークにおける最適波長割り当て, 電子情報通信学会技術研究報告, vol. 104, no. 555, (CAS2005-60), pp. 1-6, January 2005.
  • 池田 智広,松林 昭, グラフを梯子へ最小辺負荷で埋め込む多項式時間アルゴリズム, 電子情報通信学会技術研究報告, vol. 104, no. 555, (CAS2005-61), pp. 7-12, January 2005.
  • 伊藤 良輔,松林 昭, リングにおける競合的オンラインデータ移動アルゴリズム, 電子情報通信学会技術研究報告, vol. 104, no. 555, (CAS2005-62), pp. 13-17, January 2005.
  • Akira Matsubayashi, Small Congestion Embedding of Separable Graphs into Grids of the Same Size, 電子情報通信学会技術研究報告, vol. 104, no. 555, (CAS2005-63), pp. 19-24, January 2005.

2004

  • Akira Matsubayashi, Small Congestion Embedding of Separable Graphs into Grids of the Same Size, 2004ソサイエティ大会講演論文集, AS-1-4, September 2004.
  • 伊藤 良輔,松林 昭, リングネットワークにおける競合的オンラインデータ移動アルゴリズム, 電気関係学会北陸支部連合大会講演論文集, EP-3, September 2004.
  • 高井 洋明,松林 昭, 2-パスネットワークにおける最適波長割り当て, 電気関係学会北陸支部連合大会講演論文集, EP-4, September 2004.
  • Akira Matsubayashi, VLSI Layout of Trees into Grids of Minimum Width, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E87-A, no. 5, pp. 1059-1069, May 2004. (manuscript). Preliminary version appeared in SPAA 2003 (DOI:10.1145/777412.777425).

2003

  • 高井 洋明,金谷 隆志,松林 昭, キャタピラネットワークにおけるパス彩色, 電子情報通信学会技術研究報告, vol. 103, no. 326, (COMP2003-39), pp. 15-20, September 2003.
  • Akira Matsubayashi, VLSI Layout of Trees into Rectangular Grids of Small Width, Proceedings of the 15th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'03), pp. 75-84, June 2003. DOI:10.1145/777412.777425.

2002

  • Akira Matsubayashi, Hiroyuki Nakamura, and Juichi Miyamichi, Constant Congestion Embedding of Node Balanced Trees into Optimal-Sized Grids, 電子情報通信学会技術研究報告, vol. 102, no. 426, (CAS2002-86), pp. 19-24, November 2002.
  • 中塚 大樹,松林 昭, 一様ネットワークにおける厳密競合オンラインデータ管理, 電子情報通信学会技術研究報告, vol. 102, no. 258, (COMP2002-27), pp. 37-43, August 2002.

2001

  • Akira Matsubayashi, On the Complexity of Minimum Congestion Embedding of Acyclic Graphs into Ladders, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E84-A, no. 5, pp. 1218-1226, May 2001. (manuscript)

2000

  • Akira Matsubayashi and Masaya Yokota, The Complexity of Embedding of Acyclic Graphs into Grids with Minimum Congestion, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E83-A, no. 11, pp. 2390-2394, November 2000. (manuscript)
  • Akira Matsubayashi and Ryo Takasu, Minimum Congestion Embedding of Complete Binary Trees into Tori, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E83-A, no. 9, pp. 1804-1808, September 2000. (manuscript). Preliminary version appeared in COCOON 1999 (LNCS 1627).

1999

  • Akira Matsubayashi and Ryo Takasu, Minimum Congestion Embedding of Complete Binary Trees into Tori, Proceedings of the 5th Annual International Computing and Combinatorics Conference (COCOON'99), Lecture Notes in Computer Science, vol. 1627, pp. 370-378, July 1999.
  • 横田 雅也,松林 昭, 閉路を含まないグラフの格子への辺負荷最小埋め込みの計算複雑度について, 1999年電子情報通信学会総合大会講演論文集(基礎・境界), p.8, March 1999.
  • Akira Matsubayashi and Shuichi Ueno, Small Congestion Embedding of Graphs into Hypercubes, Networks, vol. 33, no. 1, pp. 71-77, January 1999. DOI:10.1002/(SICI)1097-0037(199901)33:1<71::AID-NET5>3.0.CO;2-3. (manuscript)

1998

  • 高巣 亮,松林 昭, 完全2分木のトーラスへの辺負荷最小埋め込み, 並列処理シンポジウム JSPP '98, pp. 47-54, June 1998.
  • Akira Matsubayashi and Shuichi Ueno, A Linear Time Algorithm for Constructing Proper-Path-Decomposition of Width Two, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E81-A, no. 5, pp. 729-737, May 1998. (manuscript)

1997

  • 高巣 亮,松林 昭, 完全2分木のトーラスへの辺負荷最小埋め込み, 電子情報通信学会技術研究報告, vol. 97, no. 401, (CAS97-63(CST97-22)), pp. 33-40, November 1997.

1996

  • Akira Matsubayashi and Shuichi Ueno, On the Complexity of Embedding of Graphs into Grids with Minimum Congestion, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E79-A, no. 4, pp. 469-476, April 1996.
  • 松林 昭, Graph Embedding with Small Congestion and Its Applications to Parallel and VLSI Computation, 学位論文, 東京工業大学, 1996.3 (全文)

1995

  • 松林 昭,上野 修一, グラフの幅2の真のパス分解を求める効率的アルゴリズム, 情報処理学会研究報告, vol. 95, no. 109, pp. 9-16, November 1995.
  • 松林 昭,上野 修一, グラフの格子への辺負荷最小埋め込みの計算複雑度について, 情報処理学会 第51回全国大会講演論文集(1), pp. 65-66, September 1995.

1994

  • 松林 昭,上野 修一, グラフのハイパーキューブへの辺負荷最小の埋め込み, 情報処理学会研究報告, vol. 94, no. 69, pp. 57-64, July 1994.
  Top > Publications