• link

上嶋 章宏　(UEJIMA Akihiro)　 [教員情報データベース]

学歴・職歴

• 1998(H10)年3月　豊橋技術科学大学 工学部 情報工学課程 卒業
• 2000(H12)年3月　豊橋技術科学大学大学院 工学研究科 情報工学専攻 修士課程 修了
• 2005(H17)年3月　京都大学大学院 情報学研究科 通信情報システム専攻 博士後期課程 修了　京都大学博士(情報学)
• 2005(H17)年4月　大阪電気通信大学 情報通信工学部 情報工学科 講師
• 2013(H25)年4月　大阪電気通信大学 情報通信工学部 情報工学科 准教授

所属学会等

• 日本オペレーションズ・リサーチ学会
• 電子情報通信学会
• 情報処理学会

学会活動

• 日本オペレーションズ・リサーチ学会 研究部会 「画期における最適化」 幹事 (2009, 2010年度)
• 「画期における最適化」研究会 幹事 (2011年度～) 終了
• 電子情報通信学会「Special Section on Foundations of Computer Science - New Trends in Algorithms and Theory of Computation -」 英文論文小特集編集委員会 委員(2013年度，2013年3月15日～発行まで)

研究業績リスト

• 学術論文
  
  • A. Uejima, S. Masuda, and T. Yamamoto, ``Light Up variants are NP-complete,'' IEICE Transactions on Information and Systems, Vol. E109-D, No. 3, pp. -, Mar. 2026. (Accepted for publication)
    
  • 上嶋 章宏, 木場 裕矢, 大森 潤一, 佐藤 正彬, ``一般化詰中将棋問題のEXPTIME完全性,'' 電子情報通信学会論文誌(D), Vol. J108-D, No. 11, pp.-, Nov. 2025. (採録決定)
    
  • A. Uejima, K. Oe, ``The Computational Complexity of Creek Puzzles on Several Grids,'' Journal of Information Processing, Vol. 28, pp. 911-918, December 2020.
    
  • A. Uejima, H. Suzuki, A. Okada, ``The Complexity of Generalized Pipe Link Puzzles,'' Journal of Information Processing, Vol. 25, pp. 724-729, August 2017.
    
  • A. Uejima, H. Suzuki, ``Fillmat is NP-Complete and ASP-Complete,'' Journal of Information Processing, Vol. 23, No. 3, pp. 310-316, May 2015.
    
  • A. Uejima, F. Yanagitani, S. Tsukamoto, ``The Complexity of Tantrix Match Puzzles with Four Colors,'' Journal of Information Processing, Vol. 21, No. 3, pp. 405-412, July 2013.
    
  • 上嶋 章宏, 岡田 貴裕, ``8面, 20面ダイスを用いたRolling Dice PuzzleのNP完全性,'' 電子情報通信学会論文誌(A), Vol. J94-A, No. 8, pp. 621-628, Aug 2011.
    
  • 上條 裕介, 上嶋 章宏, ``回転型セル迷路のPSPACE完全性,'' 電子情報通信学会論文誌(A), Vol. J94-A, No. 5, pp. 362-371, May 2011.
    
  • A. Uejima, H. Ito, and T. Tsukiji, ``$\overline{C_7}$-coloring problem,'' IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol. E87-A, No. 5, pp. 1243-1250, May 2004.
    
  • A. Uejima, and H. Ito, ``On H-coloring problems with H expressed by complements of cycles, bipartite graphs, and chordal graphs,'' IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol. E85-A, No. 5, pp. 1026-1030, May 2002.
    
  • A. Uejima, H. Ito, H. Uehara, and M. Yokoyama, ``A coloring problem with restrictions of adjacent colors,'' International Transactions in Operational Research, Vol. 9, No. 2, pp. 183-194, March 2002.

• 国際会議
  
  • A. Uejima, and H. Ito, ``Subdivision of the hierarchy of H-colorable graph classes by circulant graphs,'' CTW04 Workshop on Graphs and Combinatorial Optimization, pp. 232-236, Menaggio, Italy, May 2004.
    
  • A. Uejima, H. Ito, H. Uehara, and M. Yokoyama, ``Coloring problem with restrictions of adjacent colors expressed by cycles and bipartite graphs,'' 2nd Japanese-Hungarian Symposium on Discrete Mathematics and its Applications, pp. 227-236, Budapest, Hungary, April 2001.
    
  • A. Uejima, H. Ito, H. Uehara, and M. Yokoyama, ``Coloring problem with restrictions of adjacent colors,'' IFORS'99 (The International Federation of Operations Research Societies), Beijing, China, August, 1999.
    
  
  
• 国内学会・研究会
  
  • 池内 唯斗, 上嶋 章宏, ``トークンスライディング型独立集合遷移問題に対する物理的ゼロ知識証明,'' 電子情報通信学会技術研究報告(コンピュテーション研究会), Vol. 124, No. 424, COMP2024-30, pp. 29-36, March, 2025.
  • 渡邊 泰隆, 上嶋 章宏, ``絵画的迷路の生成手法に基づくGPSアートコース自動選定システムの提案,'' 第18回研究集会「組合せゲーム・パズル」, March 2024.
  • 川﨑 楽斗, 上嶋 章宏, ``ペンシルパズル「ドッチループ」の計算困難性と物理ゼロ知識証明プロトコル,'' 第17回研究集会「組合せゲーム・パズル」, March 2023.
  • 橋本 雄輝, 上嶋 章宏, ``スイッチギミックを備えたアクションゲームの計算複雑さの解明,'' 第16回研究集会「組合せゲーム・パズル」, March 2022.
    
  • 上嶋 章宏, 木場 裕矢, 大森 潤一, 佐藤 正彬, ``一般化詰中将棋問題の指数時間完全性,'' 電子情報通信学会技術研究報告(コンピュテーション研究会), Vol. 121, No. 407, COMP2021-32, pp. 8-15, March, 2022.
    
  • 上嶋 章宏, ``組合せゲーム・パズルの計算困難性と物理セキュア計算,'' 日本OR学会中国・四国支部令和3年度支部研究部会「ORと数学」第2回講演会, February 2022.
    
  • 田井 翔太, 上嶋 章宏, ``盤面を一般化した「フォービドゥン」パズルのASP完全性,'' 第13回研究集会「組合せゲーム・パズル」, March 2018.
    
  • 上嶋 章宏, ``数理パズルの計算複雑さと整数計画法による解法,'' 2017年 日本オペレーションズ・リサーチ学会 中国・四国地区SSOR (Summer Seminar in Operations Research), September 2017.（特別講演）
    
  • 大森 潤一, 木場 裕矢, 上嶋 章宏, ``一般化詰め中将棋問題のEXPTIME完全性,'' 第12回研究集会「組合せゲーム・パズル」, March 2017.
    
  • 弘中 健太, 鈴木 裕章, 上嶋 章宏, ``Corral Puzzleの整数計画法による解法と評価,'' 第11回研究集会「組合せゲーム・パズル」, March 2016.
    
  • 貴宮 京一, 鈴木 裕章, 上嶋 章宏, ``整数計画法を用いたPearl Puzzleの効率的な解法,'' 第11回研究集会「組合せゲーム・パズル」, March 2016.
    
  • 鈴木 裕章, 上嶋 章宏, ``穴を許した一般化フィルマットのASP完全性,'' 第9回ミニ研究集会「組合せゲーム・パズル」, February 2014.
    
  • 上嶋 章宏, ``一般化した迷路と将棋の数理,'' 2013年度情報処理学会関西支部定期講演会「ゲーム・パズルの数理」, November 21, 2013.
    
  • 浅野 竜男, 上嶋 章宏, ``C7-彩色可能な平面グラフにおける内周の下界値に関する考察,'' 電子情報通信学会技術研究報告(コンピュテーション研究会), Vol. 112, No. 498, pp. 31-38, March 18, 2013.
    
  • 柳谷 不比等, 上嶋 章宏, ``だまし絵迷路生成に関する複数のハミルトン閉路構成法の比較評価,'' 電子情報通信学会技術研究報告(コンピュテーション研究会), Vol. 112, No. 498, pp. 39-46, March 18, 2013.
    
  • 浅野 竜男, 上嶋 章宏, ``非隣接性を有する組合せパズルの計算複雑さ,'' 第8回ミニ研究集会「組合せゲーム・パズル」, March 2013.
    
  • 柳谷 不比等, 小林 嗣東, 上嶋 章宏, ``タイルの形状を2種に制限したTantrix MatchのNP完全性,'' 第8回ミニ研究集会「組合せゲーム・パズル」, March 2013.
    
  • 木場 裕矢, 植谷 昌博, 上嶋 章宏, ``Type-LやTを含む制限に注目したセル迷路問題の計算複雑さの解析,'' 第7回ミニ研究集会「組合せゲーム・パズル」, March 2012.
    
  • 柳谷 不比等, 塚本 翔平, 上嶋 章宏, ``Tantrixタイルを用いた Tantrix Match のNP完全性の証明,'' 第7回ミニ研究集会「組合せゲーム・パズル」, March 2012.
    
  • 舟野 勝彦, 上嶋 章宏, ``連結性を有する組合せパズルの直接符号化法を用いたSATソルバでの解法と性能評価,'' 第74回情報処理学会全国大会, 3M-2, pp. 1-445 -- 1-446, March 2012.
    
  • 木場 裕矢, 宗重 成央, 上嶋 章宏, ``色数とおじゃまぷよを制限した一般化ぷよぷよの連鎖数判定問題のNP完全性,'' 日本オペレーションズ・リサーチ学会2011年秋季研究発表会 「娯楽のOR - エンターテイメントの数理」ワークショップ, pp. 370-371, September 2011.
    
  • 木場 裕矢, 宗重 成央, 上嶋 章宏, ``色数とおじゃまぷよを制限した一般化ぷよぷよの連鎖数判定問題のNP完全性,'' 第6回ミニ研究集会「組合せゲーム・パズル」, March 2011.
    
  • 舟野 勝彦, 上嶋 章宏, ``SATソルバを用いたSpiral Galaxies Puzzlesの解法ツール,'' 第6回ミニ研究集会「組合せゲーム・パズル」, March 2011.
    
  • 上嶋 章宏, 岡田 貴裕, ``8面, 20面ダイスを用いたRolling Dice PuzzleのNP完全性,'' 第23回 回路とシステム軽井沢ワークショップ論文集, pp. 227-232, April 2010.
    
  • 上條 裕介, 上嶋 章宏, ``盤面および使用セルを考慮した回転型セル迷路のPSPACE完全性,'' 京都大学数理解析研究所 研究集会「アルゴリズムと計算機科学の数理的基盤とその応用」 数理解析研究所講究録, Vol. 1691, pp. 167-173, February 2010.
    
  • 上嶋 章宏, 安藤 立紀, ``麻雀を用いた安全な計算のプロトコル設計, '' 平成21年度 情報処理学会関西支部 支部大会講演論文集, B-04, September 2009.
    
  • 上條 裕介, 上嶋 章宏, ``回転型セル迷路のPSPACE完全性,'' 第22回 回路とシステム軽井沢ワークショップ論文集, pp. 207-212, April 2009. (発表者の上條君が奨励賞を受賞)
    
  • 岩崎 豪, 上嶋 章宏, ``ZKIPを実現するために組合せ問題を基本機能に分解する枠組み,'' 第71回情報処理学会全国大会 講演論文集(1), pp. 423-434, March 2009.
    
  • 庄司 將一, 小西 宏, 上嶋 章宏, ``Anti-WebによるH-彩色に関する新たな階層構造の導出,'' 京都大学数理解析研究所 研究集会「理論計算機科学の深化と応用」数理解析研究所講究録, Vol. 1649, pp. 195-202, February 2009.
    
  • 庄司 將一, 上嶋 章宏, ``3 < n/k < 4に対する平面グラフのn/k-彩色問題のNP完全性,'' 電子情報通信学会技術研究報告(コンピュテーション研究会), Vol. 108, No. 29, pp. 25-32, May 2008.
    
  • 井口 雄弥, 庄司 將一, 上嶋 章宏, ``n/k-彩色での階層構造間に存在する平面グラフの構成手法,'' 電子情報通信学会技術研究報告(回路とシステム研究会), Vol. 107, No. 475, pp. 13-18, January 2008.
    
  • 庄司 將一, 上嶋 章宏, ``平面グラフのn/k-彩色問題の計算複雑さ,'' 電子情報通信学会技術研究報告(コンピュテーション研究会), Vol. 107, No. 127, pp. 55-62, June 2007.
    
  • 温井 康介, 上嶋 章宏, ``六角格子, 三角格子上でのスリザーリンクのASP完全性について,'' 情報処理学会研究報告(アルゴリズム研究会), Vol. 2007, No. 23, pp. 129-136, March 2007.
    
  • 上嶋章宏, 伊藤大雄, ``H-彩色可能なグラフのクラスの階層構造の Circulant graphs による細分化,'' 情報処理学会研究報告(アルゴリズム研究会), 2004-AL-93, pp. 1-8, January 2004.
    
  • 上嶋章宏, 伊藤大雄, ``平面グラフの$\overline{C_7}$-彩色問題,'' 情報処理学会研究報告(アルゴリズム研究会), 2002-AL-86, pp. 67-74, September 2002.
    
  • 上嶋章宏, 伊藤大雄, ``平面グラフの$\overline{C_7}$-彩色問題,'' LAシンポジウム, July 2002.
    
  • 上嶋章宏, 伊藤大雄, ``補グラフが | 最大マッチング | = | 最小節点カバー |であるH-彩色問題,'' 数理最適化の理論とアルゴリズム, July 2001.
    
  • 上嶋章宏, 真田亜希子, 伊藤大雄, 上原秀幸, 横山光雄, ``circulant 制約を持った隣接色制約付き彩色問題の応用と解析,'' LAシンポジウム, January 2001.
    
  • 上嶋章宏, 伊藤大雄, 上原秀幸, 横山光雄, ``隣接色制約付き彩色問題とその性質,'' 統計数理研究所共同研究リポート『最適化：モデリングとアルゴリズム14』, Vol. 135, pp. 102-121, March 2000.
    
  • 上嶋章宏, 伊藤大雄, 上原秀幸, 横山光雄, ``隣接色制約付き彩色問題,'' 第33回SSOR (33rd Summer Seminar on Operations Research) 予稿集, pp. 36-41, August 1998.
    
  
  
• テクニカルレポート
  
  • 庄司 將一, 上嶋 章宏, ``2 < n/k < 3に対する平面グラフのn/k-彩色問題のNP完全性,'' Information Science Center Technical Report, 大阪電気通信大学 情報科学センター ISC2007-03, pp. 45-55, 2008.
    
  • 田中 義隆, 上嶋 章宏, ``六角，三角格子上での Spiral Galaxies Puzzle の計算複雑さ,'' Information Science Center Technical Report, 大阪電気通信大学 情報科学センター ISC2006-03, pp. 49-57, 2007.

担当科目

• プロジェクト活動スキル入門　(1年・前期)
• 総合教養　(1年・前期)
• コンピュータ工学2　(1年・後期)
• データベース基礎演習　(1年・後期)
• コンピュータネットワーク基礎　(2年・前期)
• 情報工学基礎実験2　(2年・通年)
• 離散数学　(3年・前期)
• アルゴリズム設計論　(3年・前期)
• プレゼミナール　(3年・後期)
• 理論計算機科学特論　(大学院・隔年後期)

 

ページのトップへ戻る