English page

川原 純

奈良先端科学技術大学院大学 情報科学研究科 大規模システム管理研究室 助教

jkawahara is.naist.jp (jkawaharaの後ろにあっとマーク)

研究テーマ:オンラインアルゴリズム(k-サーバ問題、バッファ管理問題、オンラインナップザック問題、ビンパッキング)、 列挙アルゴリズム、データ構造(BDD,ZDD)、大規模分散処理環境、ビットコインなど


全国都道府県の組合せ隣接ブロックの数え上げ・索引リストの公開

Frontier method


Publications

Journal (refereed)

  1. Ryohei Eguchi, Naoaki Ono, Hisayuki Horai, Md.Altuf-Ul Amin, Aki Morita Hirai, Jun Kawahara, Shoji Kasahara, Tomoaki Endo, Shigehiko Kanaya,
    "Classification of Alkaloid Compounds Based on Subring Skeleton (SRS) Profiling: On Finding Relationship of Compounds with Metabolic Pathways,"
    Journal of Computer Aided Chemistry, vol. 18, pp. 58-75, 2017, doi:10.2751/jcac.18.58.
  2. Jun Kawahara, Takeru Inoue, Hiroaki Iwashita, and Shin-ichi Minato,
    "Frontier-based Search for Enumerating All Constrained Subgraphs with Compressed Representation,"
    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E100-A, no. 9, pp. 1773-1784, Sep. 2017, doi:10.1587/transfun.E100.A.1773.
  3. Junki Itoi, Masahiro Sasabe, Jun Kawahara, and Shoji Kasahara,
    "An Offline Mobile Application for Automatic Evacuation Guiding in Outdoor Environments,"
    Scientific Phone Apps and Mobile Devices, vol. 3, no. 1, pp. 1-10, Jan. 2017, doi:10.1186/s41070-017-0013-1.
  4. Jun Kawahara, Koji M. Kobayashi, and Shuichi Miyazaki,
    "Better Bounds for Online k-Frame Throughput Maximization in Network Switches,"
    Theoretical Computer Science, vol. 657, part B, pp. 173-190, Jan. 2017, doi:10.1016/j.tcs.2016.10.009.
  5. Nobuhisa Komatsu, Masahiro Sasabe, Jun Kawahara, and Shoji Kasahara,
    "Automatic Evacuation Guiding Scheme Based on Implicit Interactions Between Evacuees and Their Mobile Nodes,"
    GeoInformatica, 2016 (to appear), doi:10.1007/s10707-016-0270-1.
  6. 戸田 貴久, 斎藤 寿樹, 岩下 洋哲, 川原 純, 湊 真一,
    "ZDDと列挙問題 - 最新の技法とプログラミングツール,"
    コンピュータソフトウェア, vol. 34, no. 3, pp. 97-120, 2017, doi:10.11309/jssst.34.3_97.
  7. Takeru Inoue, Hiroaki Iwashita, Jun Kawahara, and Shin-ichi Minato,
    "Graphillion: software library designed for very large sets of labeled graphs,"
    International Journal on Software Tools for Technology Transfer, pp. 57-66, Feb. 2016, doi:10.1007/s10009-014-0352-z.
  8. Jun Kawahara and Koji M. Kobayashi,
    "Optimal buffer management for 2-frame throughput maximization,"
    Computer Networks, vol. 91, pp. 804-820, Nov. 2015, doi:10.1016/j.comnet.2015.08.046.
  9. Jun Kawahara, Koji M. Kobayashi, and Tomotaka Maeda,
    "Tight analysis of priority queuing for egress traffic,"
    Computer Networks, vol. 91, pp. 614-624, Nov. 2015, doi:10.1016/j.comnet.2015.09.001.
  10. Jun Kawahara and Koji M. Kobayashi,
    "An improved lower bound for one-dimensional online unit clustering,"
    Theoretical Computer Science, vol. 600, pp. 171-173, Oct. 2015, doi:10.1016/j.tcs.2015.06.055.
    (Technical paper)
  11. Katsuhisa Yamanaka, Erik D. Demaine, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, and Takeaki Uno,
    "Swapping labeled tokens on graphs,"
    Theoretical Computer Science, vol. 586, pp. 81-94, Jun. 2015, doi:10.1016/j.tcs.2015.01.052.
  12. Takeru Inoue, Keiji Takano, Takayuki Watanabe, Jun Kawahara, Ryo Yoshinaka, Akihiro Kishimoto, Koji Tsuda, Shin-ichi Minato, and Yasuhiro Hayashi,
    "Distribution loss minimization with guaranteed error bound,"
    IEEE Transactions on Smart Grid, vol. 5, no. 1, pp. 102-111, Jan. 2014, doi:10.1109/TSG.2013.2288976.
  13. Ryo Yoshinaka, Jun Kawahara, Shuhei Denzumi, Hiroki Arimura, and Shin-ichi Minato,
    "Counterexamples to the long-standing conjecture on the complexity of BDD binary operations,"
    Information Processing Letters, vol. 112, no. 16, pp. 636-640, Aug. 2012, doi:10.1016/j.ipl.2012.05.007.
    (Technical paper)
  14. Ryo Yoshinaka, Toshiki Saitoh, Jun Kawahara, Koji Tsuruma, Hiroaki Iwashita, and Shin-ichi Minato,
    "Finding all solutions and instances of numberlink and slitherlink by ZDDs,"
    Algorithms, vol. 5, no. 2, pp. 176-213, Apr. 2012, doi:10.3390/a5020176.
  15. Wolfgang Bein, Kazuo Iwama, Jun Kawahara, Lawrence L. Larmore, and James A. Oravec,
    "A randomized algorithm for two servers in cross polytope spaces,"
    Theoretical Computer Science, vol. 412, no. 7, pp. 563-572, Feb. 2011, doi:10.1016/j.tcs.2010.08.022.
  16. Wolfgang Bein, Kazuo Iwama, and Jun Kawahara,
    "Randomized competitive analysis for two server problems,"
    Algorithms, vol. 1, no. 1, pp. 30-42, Sep. 2008, doi:10.3390/a1010030.

Conference (refereed)

  1. Joe Suzuki, and Jun Kawahara,
    "Branch and Bound for Regular Bayesian Network Structure Learning,"
    In Proceedings of the 33rd conference on Uncertainty in Artificial Intelligence (UAI 2017) (poster presentation).
    (Web)
  2. Jun Kawahara, Toshiki Saitoh, and Ryo Yoshinaka,
    "The Time Complexity of the Token Swapping Problem and Its Parallel Variants,"
    In Proceedings of the 11th International Conference and Workshops on Algorithms and Computation (WALCOM 2017), vol. 10167, pp. 448--459, 2017, doi:10.1007/978-3-319-53925-6_35.
    (Web, Preprint (ArXiv))
  3. Jun Kawahara, Takashi Horiyama, Keisuke Hotta, and Shin-ichi Minato,
    "Generating All Patterns of Graph Partitions within a Disparity Bound,"
    In Proceedings of the 11th International Conference and Workshops on Algorithms and Computation (WALCOM 2017), vol. 10167, pp. 119--131, 2017, doi:10.1007/978-3-319-53925-6_10.
    (Web)
  4. Apichanukul Worachate, Jun Kawahara, and Shoji Kasahara,
    "Accuracy Improvement for Backup Tasks in Hadoop Speculative Algorithm,"
    In Proceedings of 6th IEEE International Symposium on Cloud and Services Computing, pp. 500--507, 2016, doi:10.1109/CIT.2016.17.
    (Web)
  5. Jun Kawahara, Toshiki Saitoh, Hirofumi Suzuki, and Ryo Yoshinaka,
    "Solving the longest oneway-ticket problem and enumerating letter graphs by augmenting the two representative approaches with ZDDs,"
    Computational Intelligence in Information Systems: Proceedings of the Computational Intelligence in Information Systems Conference (CIIS 2016), vol. 532, pp. 294-305, doi:10.1007/978-3-319-48517-1_26.
    (Web)
  6. Nobuhisa Komatsu, Masahiro Sasabe, Jun Kawahara, and Shoji Kasahara,
    "Automatic evacuation guiding scheme using trajectories of mobile nodes,"
    In Proceedings of the 12th International Conference on Mobile Web and Intelligent Information Systems (MobiWis2015), vol. 9228, pp. 3-14, doi:10.1007/978-3-319-23144-0_1 (Best paper award).
  7. Jun Kawahara, Koji M. Kobayashi, and Tomotaka Maeda,
    "Tight analysis of priority queuing for egress traffic,"
    In Proceedings of the 8th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2014), vol. 8881, pp. 459-473.
    (Web)
  8. Katsuhisa Yamanaka, Erik D. Demaine, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, and Takeaki Uno,
    "Swapping labeled tokens on graphs,"
    In Proceedings of the 7th International Conference on Fun with Algorithms (FUN 2014), vol. 8496, pp. 364-375.
    (Paper)
  9. Shuhei Denzumi, Jun Kawahara, Koji Tsuda, Hiroki Arimura, Shin-ichi Minato, and Kunihiko Sadakane
    "DenseZDD: a compact and fast index for families of sets,"
    In Proceedings of the 13th International Symposium on Experimental Algorithms (SEA 2014), vol. 8504, pp. 187-198.
    (Technical paper)
  10. Jun Kawahara, Koji M. Kobayashi, and Shuichi Miyazaki,
    "Better bounds for online k-frame throughput maximization in network switches,"
    In Proceedings of the 24th International Symposium on Algorithms and Computation (ISAAC 2013), vol. 8283, pp. 218-228.
    (Web)
  11. Atsushi Takizawa, Yasufumi Takechi, Akio Ohta, Naoki Katoh, Takeru Inoue, Takashi Horiyama, Jun Kawahara, and Shin-ichi Minato,
    "Enumeration of region partitioning for evacuation planning based on ZDD,"
    In Proceedings of the International Symposium on Operations Research and its Applications (ISORA 2013), pp. 64-71.
  12. Jun Kawahara and Koji M. Kobayashi,
    "Optimal buffer management for 2-frame throughput maximization,"
    In Proceedings of the 20th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2013), vol. 8179, pp. 274-285.
    (Web)
  13. Shogo Takeuchi, Jun Kawahara, Akihiro Kishimoto, and Shin-ichi Minato,
    "Shared-memory parallel frontier-based search,"
    In Proceedings of the Seventh International Workshop on Algorithms and Computation (WALCOM 2013), vol. 7748, pp. 170-181, 10.1007/978-3-642-36065-7_17.
    (Web)
  14. Wolfgang Bein, Naoki Hatta, Nelson Hernandez-Cons, Hiro Ito, Shoji Kasahara, and Jun Kawahara,
    "An online algorithm optimally self-tuning to congestion for power management problems,"
    In Proceedings of the 9th Workshop on Approximation and Online Algorithms (WAOA 2011), vol. 7164, pp. 35-48, 10.1007/978-3-642-29116-6_4.
    (Web)
  15. Wolfgang Bein, Kazuo Iwama, and Jun Kawahara,
    "Randomized competitive analysis for two-server problems,"
    In Proceedings of the 16th annual European symposium on Algorithms (ESA 2008), vol. 5193, pp. 161-172, 10.1007/978-3-540-87744-8_14.
    (Web)
  16. Wolfgang Bein, Kazuo Iwama, Jun Kawahara, Lawrence L. Larmore, and James A. Oravec,
    "A randomized algorithm for two servers in cross polytope spaces,"
    In Proceedings of the 5th Workshop on Approximation and Online Algorithms (WAOA 2007), vol. 4927, pp. 246-259, 10.1007/978-3-540-77918-6_20.
    (Web, Paper)
  17. Takashi Horiyama, Kazuo Iwama, and Jun Kawahara,
    "Finite-state online algorithms and their automated competitive analysis,"
    In Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC 2006), vol. 4288, pp. 71-80, 10.1007/11940128_9.
    (Web, Paper, Slide)

Conference (without formal proceedings)

  1. Yu Nakahata, Jun Kawahara, Takashi Horiyama, Shoji Kasahara,
    "Enumerating All Rooted Shortest Path Forests Using Zero-suppressed Binary Decision Diagrams,"
    The 20th Korea-Japan Joint Workshop on Algorithms and Computation (WAAC 2017).
    (web)
  2. Jun Kawahara, Takashi Horiyama, Keisuke Hotta, Shin-ichi Minato,
    "Enumeration algorithms for political districting,"
    Conference of the International Federation of Classification Societies (IFCS 2017).
    (web)
  3. Keisuke Hotta, Jun Kawahara, Takashi Horiyama, Shin-ichi Minato,
    "Enumeration and evaluation for the single-seat constituency system,"
    the 21st conference of the International Federation of Operational Research Societies (IFORS 2017).
    (web)
  4. Hiroaki Iwashita, Yoshio Nakazawa, Jun Kawahara, Takeaki Uno, and Shin-ichi Minato,
    "Fast computation of the number of paths in a grid graph,"
    the 16th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCG^2 2013).
  5. Shuhei Denzumi, Jun Kawahara, Koji Tsuda, Hiroki Arimura, and Shin-ichi Minato,
    "Fast and Succinct Indices Based on Zero-Suppressed Binary Decision Diagrams,"
    the Third Workshop on Algorithms for Large-Scale Information Processing (ALSIP 2012), Nov. 2012.
  6. Takashi Horiyama, Hiro Ito, Kazuo Iwama, and Jun Kawahara,
    "Enumeration of tsume-shogi diagrams by the reverse method,"
    In Proceedings of the International Conference on Informatics Education and Research for Knowledge-Circulating Society (ICKS 2008), pp. 193-196 (poster presentation).

Technical paper (not published as a journal/conference paper)

書籍

  1. NAIST‐IS書籍出版委員会 (編集) ,
    シンギュラリティ: 限界突破を目指した最先端研究,
    近代科学社 (2016/3/3).
    (川原は7.7節を担当) (Amazon)
  2. ERATO 湊離散構造処理系プロジェクト (著), 湊真一 (編集),
    超高速グラフ列挙アルゴリズム-〈フカシギの数え方〉が拓く,組合せ問題への新アプローチ-,
    森北出版 (2015/4/8).
    (川原は4章全てと5章の一部を執筆) (Amazon)

学会誌

  1. 川原 純, 湊 真一,
    順列の圧縮列挙索引化とソーティング (<小特集>「フカシギの数え方」から広がるアルゴリズムの理工学-二分決定グラフによる離散構造処理と広がる応用分野),
    電子情報通信学会誌, vol. 97, No. 12, pp. 1086-1090, December 2014. (Web)
  2. 吉仲 亮, 岩下 洋哲, 川原 純, 斎藤 寿樹, 鶴間 浩二, 湊 真一,
    種々のリンクパズルへの応用,
    オペレーションズ・リサーチ, vol. 57, No. 11, pp. 616-622, November 2012.
  3. 井上 武, 高野 圭司, 渡辺 喬之, 川原 純, 吉仲 亮, 岸本 章宏, 津田 宏治, 湊 真一, 林 泰弘,
    フロンティア法による電力網構成技術,
    オペレーションズ・リサーチ, vol. 57, No. 11, pp. 610-615, November 2012.
  4. 川原 純, 湊 真一,
    グラフ列挙索引化技法の種々の問題への適用,
    オペレーションズ・リサーチ, vol. 57, No. 11, pp. 604-609, November 2012.
  5. 川原 純,
    私のブックマーク 「決定グラフを用いたデータ構造」,
    人工知能学会誌, vol. 27, No. 5, pp. 532-536, September 2012.
    (Web version)
  6. 川原 純, 斎藤寿樹, 湊 真一,
    ZDDを用いた新たな列挙手法(小特集「広がる列挙の技術 --- 列挙による問題解決アプローチ ---」),
    電子情報通信学会誌, vol. 95, No. 6, pp. 505-511, June 2012.
  7. 川原 純,
    ZDDを用いたパスの列挙と索引生成,
    LAシンポジウム会誌, No. 58, pp. ??-??, January 2012.

プレスリリース

企業との共同研究(終了したもの)

研究会、技術報告、国内発表(口頭、ポスター)等(一部)

○が付いた著者名が発表者。「(ポスター発表)」の記述がないものは口頭発表

受賞等

論文賞(主著者として)

論文賞(共著者として)

競争的獲得資金

講義