2023/11/15 更新

サイトウ トシキ
斎藤 寿樹
SAITOH Toshiki
Scopus 論文情報  
総論文数: 0  総Citation: 0  h-index: 11

Citation Countは当該年に発表した論文の被引用数

所属
大学院情報工学研究院 知能情報工学研究系
職名
准教授
外部リンク

研究キーワード

  • グラフアルゴリズム

研究分野

  • 情報通信 / 情報学基礎論

出身学校

  • 2005年03月   島根大学   総合理工学部   数理情報システム学科   卒業   日本国

出身大学院

  • 2010年03月   北陸先端科学技術大学院大学   情報科学研究科   博士課程・博士後期課程   修了   日本国

  • 2007年03月   北陸先端科学技術大学院大学   情報科学研究科   修士課程・博士前期課程   修了   日本国

取得学位

  • 北陸先端科学技術大学院大学  -  博士(情報科学)   2010年03月

学内職務経歴

  • 2019年04月 - 現在   九州工業大学   大学院情報工学研究院   知能情報工学研究系     准教授

  • 2017年03月 - 2019年03月   九州工業大学   大学院情報工学研究院   システム創成情報工学研究系     准教授

学外略歴

  • 2010年04月 - 2012年03月   科学技術振興機構 ERATO 湊離散構造処理系プロジェクト   研究員   日本国

所属学会・委員会

  • 2018年09月 - 2019年10月   The Review of Socionetwork Strategies 特集号編集委員会 (Springer)   ドイツ連邦共和国

  • 2013年04月 - 現在   LAシンポジウム   日本国

  • 2012年08月 - 現在   電子情報通信学会   日本国

論文

  • Sorting balls and water: Equivalence and computational complexity 招待有り 査読有り 国際誌

    Ito T., Kawahara J., Minato S.i., Otachi Y., Saitoh T., Suzuki A., Uehara R., Uno T., Yamanaka K., Yoshinaka R.

    Theoretical Computer Science   978   2023年11月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)

    Various forms of sorting problems have been studied over the years. Recently, two kinds of sorting puzzle apps have gained popularity. In these puzzles, we are given a set of bins filled with colored units, balls or water, and some empty bins. These puzzles allow us to move colored units from a bin to another when the colors involved match in some way or the target bin is empty. The goal of these puzzles is to sort all the color units in order. We investigate computational complexities of these puzzles. We first show that these two puzzles are essentially the same from the viewpoint of solvability. That is, an instance is sortable by ball-moves if and only if it is sortable by water-moves. We also show that every yes-instance has a solution of polynomial length, which implies that these puzzles belong to NP. We then show that these puzzles are NP-complete. For some special cases, we give polynomial-time algorithms. We finally consider the number of empty bins sufficient for making all instances solvable and give non-trivial upper and lower bounds in terms of the number of filled bins and the capacity of bins.

    DOI: 10.1016/j.tcs.2023.114158

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85171538418&origin=inward

  • Efficient Non-isomorphic Graph Enumeration Algorithms for Subclasses of Perfect Graphs 査読有り 国際誌

    Kawahara J., Saitoh T., Takeda H., Yoshinaka R., Yoshioka Y.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   13973 LNCS   151 - 163   2023年01月

     詳細を見る

    担当区分:責任著者   記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    Intersection graphs are well-studied in the area of graph algorithms. Some intersection graph classes are known to have algorithms enumerating all unlabeled graphs by reverse search. Since these algorithms output graphs one by one and the numbers of graphs in these classes are vast, they work only for a small number of vertices. Binary decision diagrams (BDDs) are compact data structures for various types of data and useful for solving optimization and enumeration problems. This study proposes enumeration algorithms for five intersection graph classes, which admit -bit string representations for their member graphs. Our algorithm for each class enumerates all unlabeled graphs with n vertices over BDDs representing the binary strings in time polynomial in n. Moreover, our algorithms are extended to enumerate those with constraints on the maximum (bi)clique size and/or the number of edges.

    DOI: 10.1007/978-3-031-27051-2_14

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85151054038&origin=inward

  • Path Cover Problems with Length Cost 査読有り

    Kobayashi K., Lin G., Miyano E., Saitoh T., Suzuki A., Utashima T., Yagita T.

    Algorithmica   85 ( 11 )   3348 - 3375   2023年01月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)

    For a graph G= (V, E) , a collection P of vertex-disjoint (simple) paths is called a path cover of G if every vertex v∈ V is contained in exactly one path of P. The Path Cover problem (PC for short) is to find a minimum cardinality path cover of G. In this paper, we introduce generalizations of PC, where each path is associated with a weight (cost or profit). Our problem, Minimum (Maximum) Weighted Path Cover [MinPC (MaxPC)], is defined as follows: Let U= { 0 , 1 , ⋯ , n- 1 }. Given a graph G= (V, E) and a weight function f: U→ R∪ { + ∞, - ∞} that defines a weight for each path based on its length, the objective of MinPC (MaxPC) is to find a path cover P of G such that the total weight of the paths in P is minimized (maximized). Let L be a subset of U, and PL be the set of paths such that each path is of length ℓ∈ L. We consider MinPLPC with binary cost, i.e., the cost function is f(ℓ) = 1 if ℓ∈ L; otherwise, f(ℓ) = 0. We also consider MaxPLPC with f(ℓ) = ℓ+ 1 , if ℓ∈ L; otherwise, f(ℓ) = 0. Many well-known graph theoretic problems such as the Hamiltonian Path and the Maximum Matching problems can be modeled using MinPLPC and MaxPLPC. In this paper, we first show that deciding whether MinP{ 0 , 1 , 2 }PC has a 0-weight solution is NP-complete for planar bipartite graphs of maximum degree three, and consequently, (i) for any constant σ≥ 1 , there is no polynomial-time approximation algorithm with approximation ratio σ for MinP{ 0 , 1 , 2 }PC unless P = NP, and (ii) MaxP{3,⋯,n-1}PC is NP-hard for the same graph class. Next, we present a polynomial-time algorithm for MinP{,1,⋯,k}PC on graphs with bounded treewidth for a fixed k. Lastly, we present a 4-approximation algorithm for MaxP{3,⋯,n-1}PC, which becomes a 2.5-approximation algorithm for subcubic graphs.

    DOI: 10.1007/s00453-023-01106-2

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85149424444&origin=inward

  • Overlapping Edge Unfoldings for Archimedean Solids and (Anti)prisms 査読有り 国際誌

    Shiota T., Saitoh T.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   13973 LNCS   36 - 48   2023年01月

     詳細を見る

    担当区分:最終著者   記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    Herein, we discuss the existence of overlapping edge unfoldings for Archimedean solids and (anti)prisms. Horiyama and Shoji showed that there are no overlapping edge unfoldings for all platonic solids and five shapes of Archimedean solids. The remaining five Archimedean solids were also found to have edge unfoldings that overlap. In this study, we propose a method called rotational unfolding to find an overlapping edge unfolding of a polyhedron. We show that all the edge unfoldings of an icosidodecahedron, a rhombitruncated cuboctahedron, an n-gonal Archimedean prism, and an m-gonal Archimedean antiprism do not overlap when and. Our algorithm finds three types of overlapping edge unfoldings for a snub cube, consisting of two vertices in contact. We show that an overlapping edge unfolding exists in an n-gonal Archimedean prism and an m-gonal Archimedean antiprism for and. Our results prove the existence of overlapping edge unfoldings for Archimedean solids and Archimedean (anti)prisms.

    DOI: 10.1007/978-3-031-27051-2_4

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85151057768&origin=inward

  • Sorting Balls and Water: Equivalence and Computational Complexity 査読有り 国際誌

    Takehiro Ito, Jun Kawahara, Shin-ichi Minato, Yota Otachi, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, Takeaki Uno, Katsuhisa Yamanaka, Ryo Yoshinaka

    LIPIcs–Leibniz International Proceedings in Informatics ( Schloss Dagstuhl )   226   16:1 - 16:17   2022年05月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    Italy   Sicily   2022年05月30日  -  2022年06月03日

    Various forms of sorting problems have been studied over the years. Recently, two kinds of sorting puzzle apps are popularized. In these puzzles, we are given a set of bins filled with colored units, balls or water, and some empty bins. These puzzles allow us to move colored units from a bin to another when the colors involved match in some way or the target bin is empty. The goal of these puzzles is to sort all the color units in order. We investigate computational complexities of these puzzles. We first show that these two puzzles are essentially the same from the viewpoint of solvability. That is, an instance is sortable by ball-moves if and only if it is sortable by water-moves. We also show that every yes-instance has a solution of polynomial length, which implies that these puzzles belong to NP. We then show that these puzzles are NP-complete. For some special cases, we give polynomial-time algorithms. We finally consider the number of empty bins sufficient for making all instances solvable and give non-trivial upper and lower bounds in terms of the number of filled bins and the capacity of bins.

    DOI: 10.4230/LIPIcs.FUN.2022.16

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85131245497&origin=inward

  • Path Cover Problems with Length Cost 査読有り 国際誌

    Kenya Kobayashi, Guohui Lin, Eiji Miyano, Toshiki Saitoh, Akira Suzuki, Tadatoshi Utashima, Tsuyoshi Yagita

    Lecture Notes in Computer Science ( Springer )   13174   396 - 408   2022年03月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    Indonesia   Jember   2022年03月24日  -  2022年03月26日

    DOI: 10.1007/978-3-030-96731-4_32

  • Max-Min 3-dispersion Problems 査読有り

    HORIYAMA Takashi, NAKANO Shin-ichi, SAITOH Toshiki, SUETSUGU Koki, SUZUKI Akira, UEHARA Ryuhei, UNO Takeaki, WASA Kunihiro

    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences ( 一般社団法人 電子情報通信学会 )   2021年01月

     詳細を見る

    担当区分:責任著者   記述言語:英語   掲載種別:研究論文(学術雑誌)

    <p>Given a set <i>P</i> of <i>n</i> points on which facilities can be placed and an integer <i>k</i>, we want to place <i>k</i> facilities on some points so that the minimum distance between facilities is maximized. The problem is called the <i>k</i>-dispersion problem. In this paper, we consider the 3-dispersion problem when <i>P</i> is a set of points on a plane (2-dimensional space). Note that the 2-dispersion problem corresponds to the diameter problem. We give an <i>O</i>(<i>n</i>) time algorithm to solve the 3-dispersion problem in the <i>L</i><sub>∞</sub> metric, and an <i>O</i>(<i>n</i>) time algorithm to solve the 3-dispersion problem in the <i>L</i><sub>1</sub> metric. Also, we give an <i>O</i>(<i>n</i><sup>2</sup> log <i>n</i>) time algorithm to solve the 3-dispersion problem in the <i>L</i><sub>2</sub> metric.</p>

    DOI: 10.1587/transfun.2020DMP0003

    CiNii Article

    その他リンク: https://ci.nii.ac.jp/naid/130008000342

  • Fixed-Treewidth-Efficient Algorithms for Edge-Deletion to Interval Graph Classes 査読有り

    Saitoh T., Yoshinaka R., Bodlaender H.L.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   12635 LNCS   142 - 153   2021年01月

     詳細を見る

    担当区分:筆頭著者   記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    For a graph class C, the C -Edge-Deletion problem asks for a given graph G to delete the minimum number of edges from G in order to obtain a graph in C. We study the C -Edge-Deletion problem for C the class of interval graphs and other related graph classes. It follows from Courcelle’s Theorem that these problems are fixed parameter tractable when parameterized by treewidth. In this paper, we present concrete FPT algorithms for these problems. By giving explicit algorithms and analyzing these in detail, we obtain algorithms that are significantly faster than the algorithms obtained by using Courcelle’s theorem.

    DOI: 10.1007/978-3-030-68211-8_12

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85102762814&origin=inward

  • Complexity of the maximum k-path vertex cover problem 査読有り

    Miyano E., Saitoh T., Uehara R., Yagita T., van der Zanden T.C.

    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences ( 一般社団法人 電子情報通信学会 )   E103A ( 10 )   1193 - 1201   2020年10月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)

    Copyright © 2020 The Institute of Electronics, Information and Communication Engineers This paper introduces the maximization version of the kpath vertex cover problem, called the Maximum k-Path Vertex Cover problem (MaxPkVC for short): A path consisting of k vertices, i.e., a path of length k − 1 is called a k-path. If a k-path Pk includes a vertex v in a vertex set S, then we say that v or S covers Pk. Given a graph G = (V, E) and an integer s, the goal of MaxPkVC is to find a vertex subset S ⊆ V of at most s vertices such that the number of k-paths covered by S is maximized. The problem MaxPkVC is generally NP-hard. In this paper we consider the tractability/intractability of MaxPkVC on subclasses of graphs. We prove that MaxP3VC remains NP-hard even for split graphs. Furthermore, if the input graph is restricted to graphs with constant bounded treewidth, then MaxP3VC can be solved in polynomial time.

    DOI: 10.1587/transfun.2019DMP0014

    Scopus

    CiNii Article

    CiNii Research

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85094115859&origin=inward

  • Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs 招待有り 査読有り 国際誌

    Yamazaki K., Saitoh T., Kiyomi M., Uehara R.

    Theoretical Computer Science ( ELSEVIER )   806   310 - 322   2020年02月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)

    © 2019 In this paper, a general framework for enumerating every element in a graph class is given. The main feature of this framework is that it is designed to enumerate only nonisomorphic graphs in a graph class. Applying this framework to the classes of interval graphs and permutation graphs, we give efficient enumeration algorithms for these graph classes such that each element in the class is output in a polynomial time delay. The experimental results are also given. The catalogs of graphs in these graph classes are also provided.

    DOI: 10.1016/j.tcs.2019.04.017

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85067471302&origin=inward

  • The time complexity of permutation routing via matching, token swapping and a variant 招待有り 査読有り

    Kawahara J., Saitoh T., Yoshinaka R.

    Journal of Graph Algorithms and Applications   23 ( 1 )   29 - 70   2019年01月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)

    © 2019, Brown University. All rights reserved. The problems of Permutation Routing via Matching and Token Swapping are reconfiguration problems on graphs. This paper is concerned with the complexity of those problems and a colored variant. For a given graph where each vertex has a unique token on it, those problems requirto find a shortest way to modify a token placement into another by swapping tokens on adjacent vertices. While all pairs of tokens on a matching can be exchanged at once in Permutation Routing via Matching, Token Swapping allows only one pair of tokens can be swapped. In the colored version, vertices and tokens are colored and the goal is to relocate tokenso that each vertex has a token of the same color. We investigate the timcomplexity of several restricted cases of those problems and show when those problems become tractable and remain intractable.

    DOI: 10.7155/JGAA.00483

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85067628333&origin=inward

  • Sequentially swapping colored tokens on graphs 招待有り 査読有り

    Yamanaka K., Demaine E., Horiyama T., Kawamura A., Nakano S., Okamoto Y., Saitoh T., Suzuki A., Uehara R., Uno T.

    Journal of Graph Algorithms and Applications   23 ( 1 )   3 - 27   2019年01月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)

    © 2019, Brown University. All rights reserved. We consider a puzzle consisting of colored tokens on an n-vertex graph, where each token has a distinct starting vertex and a set of allowable target vertices for it to reach, and the only allowed transformation is to "sequentially" move the chosen token along a path of the graph by swapping it with other tokens on the path.

    DOI: 10.7155/JGAA.00482

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85068442166&origin=inward

  • Special section on discrete mathematics and its applications 査読有り

    Kawachi A., Yamauchi Y., Ito T., Uchizawa K., Otachi Y., Ono H., Kimura K., Koga H., Saitoh T., Shibuya T., Takimoto E., Tanigawa S., Nuida K., Fukushima K., Fujiwara H., Mizuki T., Moriyama S., Sadakane K.

    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences   E102A ( 9 )   2019年01月

     詳細を見る

    記述言語:英語   掲載種別:記事・総説・解説・論説等(その他)

    DOI: 10.1587/transfun.E102.A.986

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85072683949&origin=inward

  • Max-Min 3-Dispersion Problems 査読有り

    Horiyama T., Nakano S., Saitoh T., Suetsugu K., Suzuki A., Uehara R., Uno T., Wasa K.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   11653 LNCS   291 - 300   2019年01月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    © Springer Nature Switzerland AG 2019. Given a set P of n points on which facilities can be placed and an integer k, we want to place k facilities on some points so that the minimum distance between facilities is maximized. The problem is called the k-dispersion problem. In this paper we consider the 3-dispersion problem when P is a set of points on a plane. Note that the 2-dispersion problem corresponds to the diameter problem. We give an O(n) time algorithm to solve the 3-dispersion problem in the (forumala presented). metric, and an O(n) time algorithm to solve the 3-dispersion problem in the (forumala presented) metric. Also we give an (forumala presented) time algorithm to solve the 3-dispersion problem in the (forumala presented) metric.

    DOI: 10.1007/978-3-030-26176-4_24

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85070237226&origin=inward

  • Colorful Frontier-Based Search: Implicit Enumeration of Chordal and Interval Subgraphs 査読有り

    Kawahara J., Saitoh T., Suzuki H., Yoshinaka R.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   11544 LNCS   125 - 141   2019年01月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    © 2019, Springer Nature Switzerland AG. This paper considers enumeration of specific subgraphs of a given graph by using a data structure called a zero-suppressed binary decision diagram (ZDD). A ZDD can represent the set of solutions quite compactly. Recent studies have demonstrated that a technique generically called frontier-based search (FBS) is a powerful framework for using ZDDs to enumerate various yet rather simple types of subgraphs. We in this paper, propose colorful FBS, an enhancement of FBS, which enables us to enumerate more complex types of subgraphs than existing FBS techniques do. On the basis of colorful FBS, we design methods that construct ZDDs representing the sets of chordal and interval subgraphs from an input graph. Computer experiments show that the proposed methods run faster than reverse search based algorithms.

    DOI: 10.1007/978-3-030-34029-2_9

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85076409280&origin=inward

  • Swapping colored tokens on graphs 招待有り 査読有り

    Yamanaka K., Horiyama T., Keil J., Kirkpatrick D., Otachi Y., Saitoh T., Uehara R., Uno Y.

    Theoretical Computer Science   729   1 - 10   2018年06月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)

    © 2018 Elsevier B.V. We investigate the computational complexity of the following problem. We are given a graph in which each vertex has an initial and a target color. Each pair of adjacent vertices can swap their current colors. Our goal is to perform the minimum number of swaps so that the current and target colors agree at each vertex. When the colors are chosen from {1,2,…,c}, we call this problem c-COLORED TOKEN SWAPPING since the current color of a vertex can be seen as a colored token placed on the vertex. We show that c-COLORED TOKEN SWAPPING is NP-complete for c=3 even if input graphs are restricted to connected planar bipartite graphs of maximum degree 3. We then show that 2-COLORED TOKEN SWAPPING can be solved in polynomial time for general graphs and in linear time for trees. Besides, we show that, the problem for complete graphs is fixed-parameter tractable when parameterized by the number of colors, while it is known to be NP-complete when the number of colors is unbounded.

    DOI: 10.1016/j.tcs.2018.03.016

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85044301802&origin=inward

  • Exact algorithms for the max-min dispersion problem 査読有り

    Akagi T., Araki T., Horiyama T., Nakano S., Okamoto Y., Otachi Y., Saitoh T., Uehara R., Uno T., Wasa K.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   10823 LNCS   263 - 272   2018年01月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    © 2018, Springer International Publishing AG, part of Springer Nature. Given a set P of n elements, and a function d that assigns a non-negative real number d(p, q) for each pair of elements (formula presented), we want to find a subset (formula presented) with (formula presented) such that (formula presented) is maximized. This is the max-min k-dispersion problem. In this paper, exact algorithms for the max-min k-dispersion problem are studied. We first show the max-min k-dispersion problem can be solved in (formula presented) time. Then, we show two special cases in which we can solve the problem quickly. Namely, we study the cases where a set of n points lie on a line and where a set of n points lie on a circle (and the distance is measured by the shortest arc length on the circle). We obtain O(n)-time algorithms after sorting.

    DOI: 10.1007/978-3-319-78455-7_20

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85046793309&origin=inward

  • Enumeration of Nonisomorphic Interval Graphs and Nonisomorphic Permutation Graphs 査読有り

    Yamazaki K., Saitoh T., Kiyomi M., Uehara R.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   10755 LNCS   8 - 19   2018年01月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    © 2018, Springer International Publishing AG, part of Springer Nature. In this paper, a general framework for enumerating every element in a graph class is given. The main feature of this framework is that it is designed to enumerate only non-isomorphic graphs in a graph class. Applying this framework to the classes of interval graphs and permutation graphs, we give efficient enumeration algorithms for these graph classes such that each element in the class is output in a polynomial time delay. The experimental results are also provided. The catalogs of graphs in these graph classes are also provided.

    DOI: 10.1007/978-3-319-75172-6_2

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85043316228&origin=inward

  • Computational complexity of robot arm simulation problems 査読有り

    Feng T., Horiyama T., Okamoto Y., Otachi Y., Saitoh T., Uno T., Uehara R.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   10979 LNCS   177 - 188   2018年01月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    © Springer International Publishing AG, part of Springer Nature 2018. We consider a simulation problem of a general mechanism by a robot arm. A robot arm can be modeled by a path P, and the target is modeled by a general graph G. Then the problem asks if there is an edge-weighted Eulerian path of G spanned by P. We first show that it is strongly NP-hard even if edge lengths are restricted. Then we consider two different variants of this problem. We first allow the edges in P to be elastic, and minimize the elastic ratio when G is a path. Second, we allow P to cover an edge of G twice or more. The problem is weakly NP-hard even if G is an edge. We thus assume that each edge of G is covered by P exactly twice, and obtain three hardness results and one polynomial-time algorithm when G and edge lengths are restricted.

    DOI: 10.1007/978-3-319-94667-2_15

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85049910939&origin=inward

  • Complexity of the Maximum k-Path Vertex Cover Problem 査読有り

    Miyano E., Saitoh T., Uehara R., Yagita T., van der Zanden T.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   10755 LNCS   240 - 251   2018年01月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    © 2018, Springer International Publishing AG, part of Springer Nature. This paper introduces the maximum version of the k-path vertex cover problem, called the Maximum k-Path Vertex Cover problem (MaxPkVC for short): A path consisting of k vertices, i.e., a path of length k-1 is called a k-path. If a k-path Pkincludes a vertex v in a vertex set S, then we say that S or v covers Pk. Given a graph G=(V,E) and an integer s, the goal of MaxPkVC is to find a vertex subset S=C of at most s vertices such that the number of k-paths covered by S is maximized. MaxPkVC is generally NP-hard. In this paper we consider the tractability/intractability of MaxPkVC on subclasses of graphs: We prove that MaxP3VC and MaxP4VC remain NP-hard even for split graphs and for chordal graphs, respectively. Furthermore, if the input graph is restricted to graphs with constant bounded treewidth, then MaxP3VC can be solved in polynomial time.

    DOI: 10.1007/978-3-319-75172-6_21

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85043347936&origin=inward

  • ZDD と列挙問題 - 最新の技法とプログラミングツール 査読有り

    戸田 貴久、斎藤 寿樹, 岩下 洋哲, 川原 純, 湊 真一

    Computer Software   34 ( 3 )   97 - 120   2017年08月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)

    Combinatorial enumeration problems are to find all combinations of items (solutions) that satisfy given constraints. There are many applications to various problems that are closely related to real-life such as power distribution network analysis. Recent researches have paid attention to a generic framework for computing various combinatorial enumeration problems through the method of efficiently constructing the data structure, ZDD, for all solutions of those problems in a top-down fashion, which is thus called top-down ZDD construction. The paper focuses on this subject and provides a comprehensive survey on algorithms that the construction is based on, an extended method for efficiently handling complicated constraints, the basics of the programming tool, TdZdd, that allows us to easily develop top-down construction-based programs, and practical programming examples of some applied problems.

    Kyutacar

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85027134284&origin=inward

  • Extending Partial Representations of Interval Graphs 査読有り

    Klavík P., Kratochvíl J., Otachi Y., Saitoh T., Vyskočil T.

    Algorithmica   78 ( 3 )   945 - 967   2017年07月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)

    © 2016, Springer Science+Business Media New York. Interval graphs are intersection graphs of closed intervals of the real-line. The well-known computational problem, called recognition, asks whether an input graph G can be represented by closed intervals, i.e., whether G is an interval graph. There are several linear-time algorithms known for recognizing interval graphs, the oldest one is by Booth and Lueker (J Comput Syst Sci 13:335–379, 1976) based on PQ-trees. In this paper, we study a generalization of recognition, called partial representation extension. The input of this problem consists of a graph G with a partial representation R ′ fixing the positions of some intervals. The problem asks whether it is possible to place the remaining interval and create an interval representation R of the entire graph G extending R ′ . We generalize the characterization of interval graphs by Fulkerson and Gross (Pac J Math 15:835–855, 1965) to extendible partial representations. Using it, we give a linear-time algorithm for partial representation extension based on a reordering problem of PQ-trees.

    DOI: 10.1007/s00453-016-0186-z

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84979285092&origin=inward

  • Fast maximum weight clique extraction algorithm: Optimal tables for branch-and-bound 査読有り

    Shimizu S., Yamaguchi K., Saitoh T., Masuda S.

    Discrete Applied Mathematics   223   120 - 134   2017年05月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)

    © 2017 Elsevier B.V. A new branch-and-bound algorithm for the maximum weight clique problem is proposed. The proposed algorithm consists of two phases, a precomputation phase and a branch-and-bound phase. In the precomputation phase, the weights of maximum weight cliques in many small subgraphs are calculated and stored in optimal tables. In the branch-and-bound phase, each problem is divided into smaller subproblems, and unnecessary subproblems are pruned using the optimal tables. We performed experiments with the proposed algorithm and five existing algorithms for several types of graphs. The results indicate that only the proposed algorithm can obtain exact solutions for all graphs and that it performs much faster than other algorithms for nearly all graphs.

    DOI: 10.1016/j.dam.2017.01.026

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85014188029&origin=inward

  • Extending Partial Representations of Proper and Unit Interval Graphs 査読有り

    Klavík P., Kratochvíl J., Otachi Y., Rutter I., Saitoh T., Saumell M., Vyskočil T.

    Algorithmica   77 ( 4 )   1071 - 1104   2017年04月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)

    © 2016, Springer Science+Business Media New York. The recently introduced problem of extending partial interval representations asks, for an interval graph with some intervals pre-drawn by the input, whether the partial representation can be extended to a representation of the entire graph. In this paper, we give a linear-time algorithm for extending proper interval representations and an almost quadratic-time algorithm for extending unit interval representations. We also introduce the more general problem of bounded representations of unit interval graphs, where the input constrains the positions of some intervals by lower and upper bounds. We show that this problem is NP-complete for disconnected input graphs and give a polynomial-time algorithm for the special class of instances, where the ordering of the connected components of the input graph along the real line is prescribed. This includes the case of partial representation extension. The hardness result sharply contrasts the recent polynomial-time algorithm for bounded representations of proper interval graphs (Balko et al. in 2013). So unless P= NP, proper and unit interval representations have vastly different structure. This explains why partial representation extension problems for these different types of representations require substantially different techniques.

    DOI: 10.1007/s00453-016-0133-z

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84975783207&origin=inward

  • Ferrers dimension of grid intersection graphs 査読有り

    Chaplick S., Hell P., Otachi Y., Saitoh T., Uehara R.

    Discrete Applied Mathematics   216   130 - 135   2017年01月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)

    © 2015 Elsevier B.V. We investigate the Ferrers dimension of classes of grid intersection graphs and show properties and characterizations. In particular, we show that (1) the grid intersection graphs form a proper subclass of the class of bipartite graphs of Ferrers dimension 4, (2) segment-ray graphs have a forbidden submatrix characterization, and (3) a bipartite graph is a unit grid intersection graph if and only if it is the intersection of two bipartite permutation graphs.

    DOI: 10.1016/j.dam.2015.05.035

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84931067125&origin=inward

  • Space-efficient and output-sensitive implementations of greedy algorithms on intervals 査読有り

    Saitoh T., Kirkpatrick D.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   10167 LNCS   320 - 332   2017年01月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    © Springer International Publishing AG 2017. We consider the space-efficient implementation of greedy algorithms for several fundamental problems on intervals. We assume a random access machine model with read-only access to input stored in Θ(n) words of memory, augmented with a random access memory (workspace) of size Θ(s) bits, where lgn ≤ s ≤ n. Our implementations are based on the efficient realization of an abstract data structure that we call a temporal priority queue that supports extract-min and advancetime operations for a static collection of entities, each of which is active for some pre-specified interval of time. This realization is a generalization of the memory-adjustable navigation pile proposed by Asano et al. in studying time-space tradeoffs for sorting. Using temporal priority queues we are able to implement familiar greedy algorithms for the maximum independent set problem and a variety of dominating set problems on intervals, using O(m(lg (sk/m) + n/s)) time and Θ(s) bits of workspace, where k is the size of output and m = min(sk, n). Choosing s = Θ(n) this achieves O(n lg k) output-sensitive time complexity for the maximum independent set problem on intervals, previously realized using Ω(n) words of workspace.

    DOI: 10.1007/978-3-319-53925-6_25

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85014136110&origin=inward

  • Solving the longest oneway-ticket problem and enumerating letter graphs by augmenting the two representative approaches with ZDDs 査読有り

    Kawahara J., Saitoh T., Suzuki H., Yoshinaka R.

    Advances in Intelligent Systems and Computing   532   294 - 305   2017年01月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    © Springer International Publishing AG 2017. Several researchers have studied subgraph enumeration algorithms that use a compressed expression for a family of sets, called a zero-suppressed binary decision diagram (ZDD), to solve subgraph optimization problems. We have two representative approaches to manipulate ZDDs effectively. One is fundamental mathematical operations on families of sets over ZDDs. The other is a direct construction method of a ZDD that represents desired subgraphs of a graph and is called frontierbased search. In this research, we augment the approaches by proposing two new operations, called disjoint join and joint join, on family algebra over ZDDs and extending the frontier-based search to enumerate subgraphs that have a given number of vertices of specified degrees. Employing the new approaches, we present enumeration algorithms for alphabet letter graphs on a given graph. Moreover, we solve a variant of the longest path problem, called the Longest Oneway-ticket Problem (LOP), that requires computing the longest trip on the railway network of the Japan Railways Group using a oneway ticket. Numerical experiments show that our algorithm solves the LOP and is faster than the existing integer programming approach for some instances.

    DOI: 10.1007/978-3-319-48517-1_26

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84994827378&origin=inward

  • Sequentially swapping colored tokens on graphs 査読有り

    Yamanaka K., Demaine E., Horiyama T., Kawamura A., Nakano S., Okamoto Y., Saitoh T., Suzuki A., Uehara R., Uno T.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   10167 LNCS   435 - 447   2017年01月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    © Springer International Publishing AG 2017. We consider a puzzle consisting of colored tokens on an nvertex graph, where each token has a distinct starting vertex and a set of allowable target vertices for it to reach, and the only allowed transformation is to “sequentially” move the chosen token along a path of the graph by swapping it with other tokens on the path. This puzzle is a variation of the Fifteen Puzzle and is solvable in O(n 3 ) token-swappings. We thus focus on the problem of minimizing the number of token-swappings to reach the target token-placement. We first give an inapproximability result of this problem, and then show polynomial-time algorithms on trees, complete graphs, and cycles.

    DOI: 10.1007/978-3-319-53925-6_34

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85014285826&origin=inward

  • The time complexity of the token swapping problem and its parallel variants 査読有り

    Kawahara J., Saitoh T., Yoshinaka R.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   10167 LNCS   448 - 459   2017年01月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    © Springer International Publishing AG 2017. The token swapping problem (TSP) and its colored version are reconfiguration problems on graphs. This paper is concerned with the complexity of the TSP and two new variants; namely parallel TSP and parallel colored TSP. For a given graph where each vertex has a unique token on it, the TSP requires to find a shortest way to modify a token placement into another by swapping tokens on adjacent vertices. In the colored version, vertices and tokens are colored and the goal is to relocate tokens so that each vertex has a token of the same color. Their parallel versions allow simultaneous swaps on non-incident edges in one step. We investigate the time complexity of several restricted cases of those problems and show when those problems become tractable and remain intractable.

    DOI: 10.1007/978-3-319-53925-6_35

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85014234196&origin=inward

  • 頂点と辺の重なりを削除するグラフレイアウト調整アルゴリズム 査読有り

    塚本 和樹, 増田 澄男, 斎藤 寿樹, 山口 一章

    電子情報通信学会論文誌   J99-A ( 12 )   471 - 479   2016年12月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)

  • A fast heuristic for the minimum weight vertex cover problem 査読有り

    Shimizu S., Yamaguchi K., Saitoh T., Masuda S.

    2016 IEEE/ACIS 15th International Conference on Computer and Information Science, ICIS 2016 - Proceedings   2016年08月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    © 2016 IEEE. Given a vertex-weighted undirected graph, to find the vertex cover of minimum weight is called minimum weight vertex cover problem (MWVCP). It is known as an NP-hard problem. In this paper, a fast heuristic for MWVCP is proposed. Our algorithm is based on a simple algorithm called 'list-heuristic.' Experimenal results show that our algorithm calculates better solutions in shorter time than approximation algorithms for MWVCP.

    DOI: 10.1109/ICIS.2016.7550782

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84987981842&origin=inward

  • Swapping labeled tokens on graphs 査読有り

    Yamanaka K., Demaine E., Ito T., Kawahara J., Kiyomi M., Okamoto Y., Saitoh T., Suzuki A., Uchizawa K., Uno T.

    Theoretical Computer Science   586   81 - 94   2015年06月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)

    © 2015 Elsevier B.V. Consider a puzzle consisting of n tokens on an n-vertex graph, where each token has a distinct starting vertex and a distinct target vertex it wants to reach, and the only allowed transformation is to swap the tokens on adjacent vertices. We prove that every such puzzle is solvable in O(n 2 ) token swaps, and thus focus on the problem of minimizing the number of token swaps to reach the target token placement. We give a polynomial-time 2-approximation algorithm for trees, and using this, obtain a polynomial-time 2α-approximation algorithm for graphs whose tree α-spanners can be computed in polynomial time. Finally, we show that the problem can be solved exactly in polynomial time on complete bipartite graphs.

    DOI: 10.1016/j.tcs.2015.01.052

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84945293281&origin=inward

  • Competitive diffusion on weighted graphs 査読有り

    Ito T., Otachi Y., Saitoh T., Satoh H., Suzuki A., Uchizawa K., Uehara R., Yamanaka K., Zhou X.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   9214   422 - 433   2015年01月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    © Springer International Publishing Switzerland 2015. Consider an undirected and vertex-weighted graph modeling a social network, where the vertices represent individuals, the edges do connections among them, and weights do levels of importance of individuals. In the competitive diffusion game, each of a number of players chooses a vertex as a seed to propagate his/her idea which spreads along the edges in the graph. The objective of every player is to maximize the sum of weights of vertices infected by his/her idea. In this paper, we study a computational problem of asking whether a pure Nash equilibrium exists in a given graph, and present several negative and positive results with regard to graph classes. We first prove that the problem is W[1]-hard when parameterized by the number of players even for unweighted graphs. We also show that the problem is NP-hard even for series-parallel graphs with positive integer weights, and is NP-hard even for forests with arbitrary integer weights. Furthermore, we show that the problem for forests of paths with arbitrary weights is solvable in pseudo-polynomial time; and it is solvable in quadratic time if a given graph is unweighted. We also prove that the problem is solvable in polynomial time for chain graphs, cochain graphs, and threshold graphs with arbitrary integer weights.

    DOI: 10.1007/978-3-319-21840-3_35

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84951793058&origin=inward

  • Swapping colored tokens on graphs 査読有り

    Yamanaka K., Horiyama T., Kirkpatrick D., Otachi Y., Saitoh T., Uehara R., Uno Y.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   9214   619 - 628   2015年01月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    © Springer International Publishing Switzerland 2015. We investigate the computational complexity of the following problem. We are given a graph in which each vertex has the current and target colors. Each pair of adjacent vertices can swap their current colors. Our goal is to perform the minimum number of swaps so that the current and target colors agree at each vertex. When the colors are chosen from {1, 2,..., c}, we call this problem c-COLORED TOKEN SWAPPING since the current color of a vertex can be seen as a colored token placed on the vertex. We show that c-COLORED TOKEN SWAPPING is NP-complete for every constant c ≥ 3 even if input graphs are restricted to connected planar bipartite graphs of maximum degree 3. We then show that 2-COLORED TOKEN SWAPPING can be solved in polynomial time for general graphs and in linear time for trees.

    DOI: 10.1007/978-3-319-21840-3_51

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84951828706&origin=inward

  • Extending partial representations of subclasses of chordal graphs 査読有り

    Klavík P., Kratochvíl J., Otachi Y., Saitoh T.

    Theoretical Computer Science   576 ( 1 )   85 - 101   2015年01月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)

    © 2015 Elsevier B.V. Chordal graphs are intersection graphs of subtrees of a tree T. We investigate the complexity of the partial representation extension problem for chordal graphs. A partial representation specifies a tree T < sup > ' < /sup > and some pre-drawn subtrees of T < sup > ' < /sup > . It asks whether it is possible to construct a representation inside a modified tree T which extends the partial representation (i.e., keeps the pre-drawn subtrees unchanged).We consider four modifications of T < sup > ' < /sup > leading to vastly different problems: (i) T=T < sup > ' < /sup > , (ii) T is a subdivision of T < sup > ' < /sup > , (iii) T is a supergraph of T < sup > ' < /sup > , and (iv) T < sup > ' < /sup > is a topological minor of T. In some cases, it is interesting to consider the complexity even when just T < sup > ' < /sup > is given and no subtree is pre-drawn. Also, we consider three well-known subclasses of chordal graphs: Proper interval graphs, interval graphs and path graphs. We give an almost complete complexity characterization. We further study the parametrized complexity of the problems when parametrized by the number of pre-drawn subtrees, the number of components of the input graph G and the size of the tree T < sup > ' < /sup > .We describe an interesting relation with integer partition problems. The problem 3-Partition is used for all NP-completeness reductions. When the space in T < sup > ' < /sup > is limited, partial representation extension of proper interval graphs is "equivalent" to the BINPACKING problem.

    DOI: 10.1016/j.tcs.2015.02.007

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84930241571&origin=inward

  • 階層グラフ描画における道の移動処理を用いた頂点順序決定法 査読有り

    的場 郁典, 増田 澄男, 荒木 徹也, 斎藤 寿樹, 山口 一章

    電子情報通信学会論文誌   J98-A ( 1 )   152 - 164   2015年01月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)

  • 辺交差数が少ない階層グラフ描画作成のためのダミー頂点共有処理 査読有り

    堀尾 明久, 増田 澄男, 荒木 徹也, 斎藤 寿樹, 山口 一章

    電子情報通信学会論文誌   J97-A ( 11 )   704 - 707   2014年11月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)

  • Exact Algorithms for B-Bandwidth Problem with Restricted B 査読有り

    Hiroshi Yukumoto, Toshiki Saitoh, Kazuaki Yamaguchi, and Sumio Masuda

    Proceedings of the KOREA-JAPAN Joint Workshop on Algorithms and Computation   44 - 49   2014年07月

     詳細を見る

    担当区分:責任著者   記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    Kyutacar

  • Approximating the path-distance-width for AT-free graphs and graphs in related classes 査読有り

    Otachi Y., Saitoh T., Yamanaka K., Kijima S., Okamoto Y., Ono H., Uno Y., Yamazaki K.

    Discrete Applied Mathematics   168   69 - 77   2014年05月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)

    We consider the problem of determining the path-distance-width for AT-free graphs and graphs in related classes such as k-cocomparability graphs, proper interval graphs, cobipartite graphs, and cochain graphs. We first show that the problem is NP-hard even for cobipartite graphs, and thus for AT-free graphs. Next we present simple approximation algorithms with constant approximation ratios for AT-free graphs and graphs in the related graph classes mentioned above. For instance, our algorithm for AT-free graphs has approximation factor 3 and runs in linear time. We also show that the problem is solvable in polynomial time for cochain graphs, which form a subclass of the class of proper interval graphs. © 2013 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.dam.2012.11.015

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84894638703&origin=inward

  • 階層グラフの直交描画アルゴリズム 査読有り

    荒木 徹也, 増田 澄男, 的場 郁典, 山口 一章, 斎藤 寿樹

    電子情報通信学会論文誌   J97-A ( 3 )   178 - 196   2014年03月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)

  • Swapping labeled tokens on graphs 査読有り

    Yamanaka K., Demaine E., Ito T., Kawahara J., Kiyomi M., Okamoto Y., Saitoh T., Suzuki A., Uchizawa K., Uno T.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   8496 LNCS   364 - 375   2014年01月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    Consider a puzzle consisting of n tokens on an n-vertex graph, where each token has a distinct starting vertex and a distinct target vertex it wants to reach, and the only allowed transformation is to swap the tokens on adjacent vertices. We prove that every such puzzle is solvable in O(n 2 ) token swaps, and thus focus on the problem of minimizing the number of token swaps to reach the target token placement. We give a polynomial-time 2-approximation algorithm for trees, and using this, obtain a polynomial-time 2α-approximation algorithm for graphs whose tree α-spanners can be computed in polynomial time. Finally, we show that the problem can be solved exactly in polynomial time on complete bipartite graphs. © 2014 Springer International Publishing.

    DOI: 10.1007/978-3-319-07890-8_31

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84903698259&origin=inward

  • Intersection dimension of bipartite graphs 査読有り

    Chaplick S., Hell P., Otachi Y., Saitoh T., Uehara R.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   8402 LNCS   323 - 340   2014年01月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    We introduce a concept of intersection dimension of a graph with respect to a graph class. This generalizes Ferrers dimension, boxicity, and poset dimension, and leads to interesting new problems. We focus in particular on bipartite graph classes defined as intersection graphs of two kinds of geometric objects. We relate well-known graph classes such as interval bigraphs, two-directional orthogonal ray graphs, chain graphs, and (unit) grid intersection graphs with respect to these dimensions. As an application of these graph-theoretic results, we show that the recognition problems for certain graph classes are NP-complete. © 2014 Springer International Publishing Switzerland.

    DOI: 10.1007/978-3-319-06089-7_23

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84958545366&origin=inward

  • Extending partial representations of proper and unit interval graphs 査読有り

    Klavík P., Kratochvíl J., Otachi Y., Rutter I., Saitoh T., Saumell M., Vyskočil T.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   8503 LNCS   253 - 264   2014年01月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    The recently introduced problem of extending partial interval representations asks, for an interval graph with some intervals pre-drawn by the input, whether the partial representation can be extended to a representation of the entire graph. In this paper, we give a linear-time algorithm for extending proper interval representations and an almost quadratic-time algorithm for extending unit interval representations. We also introduce the more general problem of bounded representations of unit interval graphs, where the input constrains the positions of intervals by lower and upper bounds. We show that this problem is NP-complete for disconnected input graphs and give a polynomial-time algorithm for a special class of instances, where the ordering of the connected components of the input graph along the real line is fixed. This includes the case of partial representation extension. The hardness result sharply contrasts the recent polynomial-time algorithm for bounded representations of proper interval graphs [Balko et al. ISAAC'13]. So unless P = NP, proper and unit interval representations have very different structure. This explains why partial representation extension problems for these different types of representations require substantially different techniques. © 2014 Springer International Publishing.

    DOI: 10.1007/978-3-319-08404-6_22

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84904182161&origin=inward

  • The complexity of the stamp folding problem 査読有り

    Umesato T., Saitoh T., Uehara R., Ito H., Okamoto Y.

    Theoretical Computer Science   497   13 - 19   2013年07月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)

    There are many folded states consistent with a given mountain-valley pattern of equidistant creases on a long paper strip. We would like to fold a paper strip such that the number of paper layers between each pair of hinged paper segments, called the crease width at the crease point, is minimized. This problem is called the stamp folding problem and there are two variants of this problem: minimization of the maximum crease width, and minimization of the total crease width. This optimization problem was recently introduced and investigated from the viewpoint of the counting problem. However, its computational complexity is not known. In this paper, we first show that the minimization problem of the maximum crease width is strongly NP-complete. Hence we cannot solve the problem in polynomial time unless P=NP. We next propose an algorithm that solves the minimization problem. The algorithm itself is a straightforward one, but its analysis is not trivial. We show that this algorithm runs in O((k+1) k n) time where n is the number of creases and k is the total crease width. © 2012 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.tcs.2012.08.006

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84881124972&origin=inward

  • Optimal Table Method for Finding the Maximum Weight Clique 査読有り

    Satoshi Shimizu, Kazuaki Yamaguchi, Toshiki Saitoh, and Sumio Masuda

    Proceedings of the 13th International Conference on Applied Computer Science (ACS'13)   84 - 90   2013年04月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

  • Reconstruction algorithms for permutation graphs and distance-hereditary graphs 査読有り

    Kiyomi M., Saitoh T., Uehara R.

    IEICE Transactions on Information and Systems   E96-D ( 3 )   426 - 432   2013年01月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)

    PREIMAGE CONSTRUCTION problem by Kratsch and Hemaspaandra naturally arose from the famous graph reconstruction conjecture. It deals with the algorithmic aspects of the conjecture. We present an O(n 8 ) time algorithm for PREIMAGE CONSTRUCTION on permutation graphs and an O(n 4 (n + m)) time algorithm for PREIMAGE CONSTRUCTION on distance-hereditary graphs, where n is the number of graphs in the input, and m is the number of edges in a preimage. Since each graph of the input has n - 1 vertices and O(n 2 ) edges, the input size is O(n 3 ) (, or O(nm)). There are polynomial time isomorphism algorithms for permutation graphs and distance-hereditary graphs. However the number of permutation (distance-hereditary) graphs obtained by adding a vertex to a permutation (distance-hereditary) graph is generally exponentially large. Thus exhaustive checking of these graphs does not achieve any polynomial time algorithm. Therefore reducing the number of preimage candidates is the key point. Copyright © 2013 The Institute of Electronics, Information and Communication Engineers.

    DOI: 10.1587/transinf.E96.D.426

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84878242965&origin=inward

  • Extending partial representations of subclasses of chordal graphs 査読有り

    Klavík P., Kratochvíl J., Otachi Y., Saitoh T.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   7676 LNCS   444 - 454   2012年12月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    Chordal graphs are intersection graphs of subtrees in a tree. We investigate complexity of the partial representation extension problem for chordal graphs. A partial representation specifies a tree T′ and some pre-drawn subtrees. It asks whether it is possible to construct a representation inside a modified tree T which extends the partial representation (keeps the pre-drawn subtrees unchanged). We consider four modifications of T′ and get vastly different problems. In some cases, the problem is interesting even if just T′ is given and no subtree is pre-drawn. Also, we consider three well-known subclasses of chordal graphs: Proper interval graphs, interval graphs and path graphs. We give an almost complete complexity characterization. In addition, we study parametrized complexity by the number of predrawn subtrees, the number of components and the size of the tree T′. We describe an interesting relation with integer partition problems. The problem3-PARTITION is used in theNP-completeness reductions. The BINPACKING problem is closely related to the extension of interval graphswhen space in T′ is limited, and we obtain "equivalency" with BINPACKING. © Springer-Verlag 2012.

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84871579384&origin=inward

  • Maximum-Profit Rooted Not-Necessarily-Spanning Tree Problem 査読有り

    Eishi Chiba, Yusuke Abe, Toshiki Saitoh, Takao Kageyama, Hiroki Koga and Takashi Kobayashi

    The IEEE International Conference on Industrial Engineering and Engineering Management (IEEM)   1359 - 1363   2012年12月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

  • Some Improvements on Kumlander's Maximum Weight Clique Extraction Algorithm 査読有り

    Satoshi Shimizu, Kazuaki Yamaguchi, Toshiki Saitoh, and Sumio Masuda

    Proceedings of the International Conference on Electrical, Computer, Electronics and Communication Engineering (ICECECE 2012)   ( 72 )   307 - 311   2012年12月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    Thailand   Phuket  

  • Subgraph isomorphism in graph classes 査読有り

    Kijima S., Otachi Y., Saitoh T., Uno T.

    Discrete Mathematics   312 ( 21 )   3164 - 3173   2012年11月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)

    We investigate the computational complexity of the following restricted variant of Subgraph Isomorphism: given a pair of connected graphs G=(V G ,E G ) and H=(V H ,E H ), determine if H is isomorphic to a spanning subgraph of G. The problem is NP-complete in general, and thus we consider cases where G and H belong to the same graph class such as the class of proper interval graphs, of trivially perfect graphs, and of bipartite permutation graphs. For these graph classes, several restricted versions of Subgraph Isomorphism such as Hamiltonian Path, Clique, Bandwidth, and Graph Isomorphism can be solved in polynomial time, while these problems are hard in general. © 2012 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.disc.2012.07.010

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84865102283&origin=inward

  • 種々のリンクパズルへの応用

    吉仲 亮, 岩下 洋哲, 川原 純, 斎藤 寿樹, 鶴間 浩二, 湊 真一

    オペレーションズ・リサーチ ( OR学会 )   57 ( 11 )   616 - 622   2012年11月

     詳細を見る

    記述言語:日本語   掲載種別:記事・総説・解説・論説等(学術雑誌)

  • Efficient enumeration of the directed binary perfect phylogenies from incomplete data 査読有り

    Kiyomi M., Okamoto Y., Saitoh T.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   7276 LNCS   248 - 259   2012年08月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    We study a character-based phylogeny reconstruction problem when an incomplete set of data is given. More specifically, we consider the situation under the directed perfect phylogeny assumption with binary characters in which for some species the states of some characters are missing. Our main object is to give an efficient algorithm to enumerate (or list) all perfect phylogenies that can be obtained when the missing entries are completed. While a simple branch-and-bound algorithm (B & B) shows a theoretically good performance, we propose another approach based on a zero-suppressed binary decision diagram (ZDD). Experimental results on randomly generated data exhibit that the ZDD approach outperforms B & B. We also prove that counting the number of phylogenetic trees consistent with a given data is #P-complete, thus providing an evidence that an efficient random sampling seems hard. © 2012 Springer-Verlag.

    DOI: 10.1007/978-3-642-30850-5_22

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84864344991&origin=inward

  • Bipartite Permutation Graphs are Reconstructible 査読有り

    Masashi Kiyomi, Toshiki Saitoh, and Ryuhei Uehara

    Discrete Mathematics, Algorithms and Applications   4 ( 3 )   1 - 14   pp1250039:1-14   2012年08月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)

    DOI: 10.1142/S1793830912500395

  • Finding all solutions and instances of numberlink and slitherlink by ZDDs 査読有り

    Yoshinaka R., Saitoh T., Kawahara J., Tsuruma K., Iwashita H., Minato S.

    Algorithms   5 ( 2 )   176 - 213   2012年06月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)

    Link puzzles involve finding paths or a cycle in a grid that satisfy given local and global properties. This paper proposes algorithms that enumerate solutions and instances of two link puzzles, Slitherlink and Numberlink, by zero-suppressed binary decision diagrams (ZDDs). A ZDD is a compact data structure for a family of sets provided with a rich family of set operations, by which, for example, one can easily extract a subfamily satisfying a desired property. Thanks to the nature of ZDDs, our algorithms offer a tool to assist users to design instances of those link puzzles. © 2012 by the authors.

    DOI: 10.3390/a5020176

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84866942600&origin=inward

  • ZDDを用いた新たな列挙手法

    川原 純, 斎藤 寿樹, 湊 真一

    電子情報通信学会学会誌 ( 電子情報通信学会 )   95 ( 6 )   505 - 511   2012年06月

     詳細を見る

    担当区分:責任著者   記述言語:日本語   掲載種別:記事・総説・解説・論説等(学術雑誌)

  • Random generation and enumeration of bipartite permutation graphs 査読有り

    Saitoh T., Otachi Y., Yamanaka K., Uehara R.

    Journal of Discrete Algorithms   10 ( 1 )   84 - 97   2012年01月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)

    Connected bipartite permutation graphs without vertex labels are investigated. First, the number of connected bipartite permutation graphs of n vertices is given. Based on the number, a simple algorithm that generates a connected bipartite permutation graph uniformly at random up to isomorphism is presented. Finally an enumeration algorithm of connected bipartite permutation graphs is proposed. The algorithm is based on reverse search, and it outputs each connected bipartite permutation graph in O(1) time. © 2011 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.jda.2011.11.001

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84855564873&origin=inward

  • Approximability of the path-distance-width for AT-free graphs 査読有り

    Otachi Y., Saitoh T., Yamanaka K., Kijima S., Okamoto Y., Ono H., Uno Y., Yamazaki K.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   6986 LNCS   271 - 282   2011年12月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    The path-distance-width of a graph measures how close the graph is to a path. We consider the problem of determining the path-distance-width for graphs with chain-like structures such as k-cocomparability graphs, AT-free graphs, and interval graphs. We first show that the problem is NP-hard even for a very restricted subclass of AT-free graphs. Next we present simple approximation algorithms with constant approximation ratios for graphs with chain-like structures. For instance, our algorithm for AT-free graphs has approximation factor 3 and runs in linear time. We also show that the problem is solvable in polynomial time for the class of cochain graphs, which is a subclass of the class of proper interval graphs. © 2011 Springer-Verlag.

    DOI: 10.1007/978-3-642-25870-1_25

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84855408658&origin=inward

  • Complexity of the stamp folding problem 査読有り

    Umesato T., Saitoh T., Uehara R., Ito H.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   6831 LNCS   311 - 321   2011年08月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    For a given mountain-valley pattern of equidistant creases on a long paper strip, there are many folded states consistent with the pattern. Among these folded states, we like to fold a paper so that the number of the paper layers between each pair of hinged paper segments, which is called the crease width at the crease point, is minimized. This problem is called the stamp folding problem and there are two variants of this problem; minimization of the maximum crease width, and minimization of the total crease width. This optimization problem is recently introduced and investigated from the viewpoint of the counting problem. However, its computational complexity is not known. In this paper, we first show that the minimization problem of the maximum crease width is strongly NP-complete. Hence we cannot solve the problem in polynomial time unless P=NP. We next propose an algorithm that solves the minimization problem. The algorithm itself is a straightforward one, but its analysis is not trivial. We show that this algorithm runs in O(n 2 (n+k/k)) time where n is the number of creases and k is the total crease width. That is, the algorithm runs in O(n k+2 ) time for a constant k. Hence we can solve the problem efficiently for a small constant k. © 2011 Springer-Verlag.

    DOI: 10.1007/978-3-642-22616-8_25

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=80051995876&origin=inward

  • Subgraph Isomorphism in Graph Classes 査読有り

    Shuji Kijima, Yota Otachi, Toshiki Saitoh, and Takeaki Uno

    Proceedings of the KOREA-JAPAN Joint Workshop on Algorithms and Computation (WAAC 2011)   185 - 192   2011年07月

     詳細を見る

    担当区分:責任著者   記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    Kore   Busan  

  • Voronoi game on a path 査読有り

    Kiyomi M., Saitoh T., Uehara R.

    IEICE Transactions on Information and Systems   E94-D ( 6 )   1185 - 1189   2011年01月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)

    The Voronoi game is a two-person perfect information game modeling a competitive facility location. The original version of the game is played on a continuous domain. Only two special cases (1- dimensional case and 1-round case) have been extensively investigated. Recently, the discrete Voronoi game of which the game arena is given as a graph was introduced. In this note, we give a complete analysis of the discrete Voronoi game on a path. There are drawing strategies for both the first and the second players, except for some trivial cases. Copyright © 2011 The Institute of Electronics, Information and Communication Engineers.

    DOI: 10.1587/transinf.E94.D.1185

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=79957942846&origin=inward

  • Bipartite permutation graphs are reconstructible 査読有り

    Kiyomi M., Saitoh T., Uehara R.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   6509 LNCS ( PART 2 )   362 - 373   2010年12月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    The graph reconstruction conjecture is a long-standing open problem in graph theory. The conjecture has been verified for all graphs with at most 11 vertices. Further, the conjecture has been verified for regular graphs, trees, disconnected graphs, unit interval graphs, separable graphs with no pendant vertex, outer-planar graphs, and unicyclic graphs. We extend the list of graph classes for which the conjecture holds. We give a proof that bipartite permutation graphs are reconstructible. © 2010 Springer-Verlag.

    DOI: 10.1007/978-3-642-17461-2_29

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=78650847364&origin=inward

  • Reconstruction of interval graphs 査読有り

    Kiyomi M., Saitoh T., Uehara R.

    Theoretical Computer Science   411 ( 43 )   3859 - 3866   2010年10月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)

    The graph reconstruction conjecture is a long-standing open problem in graph theory. There are many algorithmic studies related to it, such as DECK CHECKING, LEGITIMATE DECK, PREIMAGE CONSTRUCTION, and PREIMAGE COUNTING. We study these algorithmic problems by limiting the graph class to interval graphs. Since we can solve GRAPH ISOMORPHISM for interval graphs in polynomial time, DECK CHECKING for interval graphs is easily done in polynomial time. Since the number of interval graphs that can be obtained from an interval graph by adding a vertex and edges incident to it can be exponentially large, developing polynomial time algorithms for LEGITIMATE DECK, PREIMAGE CONSTRUCTION, and PREIMAGE COUNTING on interval graphs is not trivial. We present that these three problems are solvable in polynomial time on interval graphs. © 2010 Elsevier B.V. All rights reserved.

    DOI: 10.1016/j.tcs.2010.07.006

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=77957301685&origin=inward

  • Random Generation and Enumeration of Proper Interval Graphs 査読有り

    Toshiki Saitoh, Katsuhisa Yamanaka, Masashi Kiyomi, and Ryuhei Uehara

    IEICE Transactions on Information and Systems   E93-D ( 7 )   1816 - 1823   2010年07月

     詳細を見る

    担当区分:責任著者   記述言語:英語   掲載種別:研究論文(学術雑誌)

    Kyutacar

  • Reconstruction algorithm for permutation graphs 査読有り

    Kiyomi M., Saitoh T., Uehara R.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   5942 LNCS   125 - 135   2010年03月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    PREIMAGE CONSTRUCTION problem by Kratsch and Hemaspaandra naturally arose from the famous graph reconstruction conjecture. It deals with the algorithmic aspects of the conjecture. We present an O(n 8 ) time algorithm for PREIMAGE CONSTRUCTION on permutation graphs, where n is the number of graphs in the input. Since each graph of the input has n-1 vertices and O(n 2 ) edges, the input size is O(n 3 ). There are polynomial time isomorphism algorithms for permutation graphs. However the number of permutation graphs obtained by adding a vertex to a permutation graph is generally exponentially large. Thus exhaustive checking of these graphs does not achieve any polynomial time algorithm. Therefore reducing the number of preimage candidates is the key point. © 2010 Springer.

    DOI: 10.1007/978-3-642-11440-3_12

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=77949601465&origin=inward

  • Random generation and enumeration of proper interval graphs 査読有り

    Saitoh T., Yamanaka K., Kiyomi M., Uehara R.

    IEICE Transactions on Information and Systems   E93-D ( 7 )   1816 - 1823   2010年01月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    We investigate connected proper interval graphs without vertex labels. We first give the number of connected proper interval graphs of n vertices. Using this result, a simple algorithm that generates a connected proper interval graph uniformly at random up to isomorphism is presented. Finally an enumeration algorithm of connected proper interval graphs is proposed. The algorithm is based on reverse search, and it outputs each connected proper interval graph in O(1) time. Copyright © 2010 The Institute of Electronics, Information and Communication Engineers.

    DOI: 10.1587/transinf.E93.D.1816

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=77956026084&origin=inward

  • Random Generation and Enumeration of Bipartite Permutation Graphs 査読有り

    Toshiki Saitoh, Yota Otachi, Katsuhisa Yamanaka, and Ryuhei Uehara

    Lecture Notes in Computer Scinece (The 20th International Symposium on Algorithms and Computation (ISAAC 2009))   5878   1104 - 1113   2009年12月

     詳細を見る

    担当区分:責任著者   記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    USA   Hawaii  

  • Random generation and enumeration of bipartite permutation graphs 査読有り

    Saitoh T., Otachi Y., Yamanaka K., Uehara R.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   5878 LNCS   1104 - 1113   2009年12月

     詳細を見る

    担当区分:筆頭著者   記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    Connected bipartite permutation graphs without vertex labels are investigated. First, the number of connected bipartite permutation graphs of n vertices is given. Based on the number, a simple algorithm that generates a connected bipartite permutation graph uniformly at random up to isomorphism is presented. Finally an enumeration algorithm of connected bipartite permutation graphs is proposed. The algorithm is based on the reverse search, and it outputs each connected bipartite permutation graph in time. © 2009 Springer-Verlag Berlin Heidelberg.

    DOI: 10.1007/978-3-642-10631-6_111

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=75649149156&origin=inward

  • Reconstruction of interval graphs 査読有り

    Kiyomi M., Saitoh T., Uehara R.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   5609 LNCS   106 - 115   2009年12月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    The graph reconstruction conjecture is a long-standing open problem in graph theory. There are many algorithmic studies related it besides mathematical studies, such as DECK CHECKING, LEGITIMATE DECK, PREIMAGE CONSTRUCTION, and PREIMAGE COUNTING. We study these algorithmic problems limiting the graph class to interval graphs. Since we can solve GRAPH ISOMORPHISM for interval graphs in polynomial time, DECK CHECKING for interval graphs is easily done in polynomial time. Since the number of interval graphs that can be obtained from an interval graph by adding a vertex and edges incident to it can be exponentially large, developing polynomial time algorithms for LEGITIMATE DECK, PREIMAGE CONSTRUCTION, and PREIMAGE COUNTING on interval graphs is not trivial. We present that these three problems are solvable in polynomial time on interval graphs. © 2009 Springer Berlin Heidelberg.

    DOI: 10.1007/978-3-642-02882-3_12

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=76249116144&origin=inward

  • Random generation and enumeration of proper interval graphs 査読有り

    Saitoh T., Yamanaka K., Kiyomi M., Uehara R.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   5431 LNCS   177 - 189   2009年07月

     詳細を見る

    担当区分:筆頭著者   記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    We investigate connected proper interval graphs without vertex labels. We first give the number of connected proper interval graphs of n vertices. Using it, a simple algorithm that generates a connected proper interval graph uniformly at random up to isomorphism is presented. Finally an enumeration algorithm of connected proper interval graphs is proposed. The algorithm is based on the reverse search, and it outputs each connected proper interval graph in O(1) time. © Springer-Verlag Berlin Heidelberg 2009.

    DOI: 10.1007/978-3-642-00202-1_16

    Scopus

    その他リンク: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=67650489347&origin=inward

  • Reconstruction of Interval Graphs 査読有り

    Masashi Kiyomi, Toshiki Saitoh, and Ryuhei Uehara

    Lecture Notes in Computer Science (The 15th International Computing and Combinatorics Conference)   5609   106 - 115   2009年07月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    USA   New York  

  • Simple Efficient Algorithm for MPQ-tree of an Interval Graph 査読有り

    Toshiki Saitoh, Masashi Kiyomi, and Ryuhei Uehara

    Proceedings of the KOREA-JAPAN Joint Workshop on Algorithms and Computation (WAAC 2007)   121 - 126   2007年08月

     詳細を見る

    担当区分:責任著者   記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)

    Korea   Gwangju  

    Kyutacar

▼全件表示

著書

  • 超高速グラフ列挙アルゴリズム-〈フカシギの数え方〉が拓く,組合せ問題への新アプローチ-

    湊 真一(編), ERATO湊離散構造処理系プロジェクト(著)(共著 ,  範囲: 2章,5章)

    森北出版  2015年04月  ( ISBN:978-4-6278-5261-7

     詳細を見る

    記述言語:日本語

口頭発表・ポスター発表等

  • Finding Path Decompositions for Efficient Dynamic Programming

    Tomoya Doi

    Symposium on Applied Engineering and Sciences (SAES2022)  2022年12月 

     詳細を見る

    開催期間: 2022年12月12日 - 2022年12月14日   記述言語:英語   開催地:オンライン  

  • 理想グラフの部分クラスに対する非同型グラフ列挙アルゴリズム

    武田 浩和

    アルゴリズム研究会 

     詳細を見る

    開催期間: 2022年11月17日 - 2022年11月18日   記述言語:日本語   開催地:Kochi Startup BASE(高知)+オンライン   国名:日本国  

  • フロンティア法を用いたペントミノパズルの解の列挙

    藤岡 祐太

    日本オペレーションズリサーチ学会九州支部「若手OR研究交流会2022」  2022年10月 

     詳細を見る

    開催期間: 2022年10月29日   記述言語:日本語   開催地:福岡大学   国名:日本国  

  • タンパク質連接ネットワークの中心性とランダムコイル指標の関係

    有吉 優聖

    日本オペレーションズリサーチ学会九州支部「若手OR研究交流会2022」  2022年10月 

     詳細を見る

    開催期間: 2022年10月29日   記述言語:日本語   開催地:福岡大学   国名:日本国  

  • 株価騰落を用いた株価変動が類似する企業グループの抽出

    草野 敦也

    第30回電子情報通信学会九州支部学生会講演会  2022年09月  電子情報通信学会

     詳細を見る

    開催期間: 2022年09月22日   記述言語:日本語   開催地:オンライン   国名:日本国  

  • 区間グラフを用いた時系列データ解析手法の提案

    後藤 廣樹

    第30回電子情報通信学会九州支部学生会講演会  2022年09月  電子情報通信学会

     詳細を見る

    開催期間: 2022年09月22日   記述言語:日本語   開催地:オンライン   国名:日本国  

  • 複数車両の配送計画アルゴリズムとその応用

    岩崎 巧実

    第30回電子情報通信学会九州支部学生会講演会  2022年09月  電子情報通信学会

     詳細を見る

    開催期間: 2022年09月22日   記述言語:日本語   開催地:オンライン   国名:日本国  

  • Path cover problems with length cost.

    Eiji Miyano

    International Conference and Workshop on Algorithms and Computation(WALCOM 2022) 

     詳細を見る

    開催期間: 2022年03月24日 - 2022年03月26日   記述言語:英語   開催地:オンライン  

  • Computational Complexity of Ball/Water Sort Puzzles

    上原 隆平

    組合せゲーム・パズルプロジェクト (CGP) 研究集会 

     詳細を見る

    開催期間: 2022年03月07日 - 2022年03月08日   記述言語:日本語   開催地:オンライン  

  • 一人ですべてのマッチョを笑顔にする声の掛け方に関する研究

    田崎 鈴

    組合せゲーム・パズルプロジェクト (CGP) 研究集会 

     詳細を見る

    開催期間: 2022年03月07日 - 2022年03月08日   記述言語:日本語   開催地:オンライン  

  • アルキメデスの(反)角柱の重なりを持つ辺展開図

    塩田 拓海

    冬のLAシンポジウム 

     詳細を見る

    開催期間: 2022年02月01日 - 2022年02月03日   記述言語:日本語   開催地:オンライン  

  • 長さコスト付きパスカバー最大化問題の近似アルゴリズム

    宮野 英次

    冬のLAシンポジウム 

     詳細を見る

    開催期間: 2022年02月01日 - 2022年02月03日   記述言語:日本語   開催地:オンライン  

  • Fixed-Treewidth-Efficient Algorithms for Edge-Deletion to Intersection Graph Classes

    Toshiki Saitoh

    International Conference and Workshop on Algorithms and Computation(WALCOM 2021) 

     詳細を見る

    開催期間: 2021年02月28日 - 2021年03月02日   記述言語:英語   開催地:Yangon(オンライン)   国名:ミャンマー連邦  

  • An Efficient Algorithm for Slitherlink by ZDDs

    Tatsuki Shingai

    International Symposium on Applied Engineering and Sciences (SAES2020)  2020年12月 

     詳細を見る

    開催期間: 2020年12月12日 - 2020年12月19日   記述言語:英語   開催地:オンライン  

  • 長さコスト付きパスカバー最大化問題に対する近似アルゴリズム

    小林賢也

    電気・情報関係学会九州支部連合大会 

     詳細を見る

    開催期間: 2020年09月27日   記述言語:日本語   開催地:九州産業大学  

  • Treedepth Problemに対する厳密解アルゴリズム

    高瀬 敏行

    第28回電子情報通信学会九州支部学生会講演会 

     詳細を見る

    開催期間: 2020年09月19日   記述言語:日本語   開催地:オンライン  

  • 省領域マルチセットソーティングアルゴリズムの開発と実装

    高瀬 敏行

    日本オペレーションズリサーチ学会九州支部「若手OR研究交流会2019」 

     詳細を見る

    開催期間: 2019年10月26日 - 2019年10月27日   記述言語:日本語   開催地:福岡工業大学FITセミナー  

  • Universal Sequence of Adjacent Transpositions

    Takehiro Ito

    電子情報通信学会コンピュテーション研究会 

     詳細を見る

    開催期間: 2019年09月02日   記述言語:英語   開催地:岡山大学津島キャンパス  

  • 二分決定図を用いた部分弦グラフと部分区間グラフの列挙

    川原 純

    電子情報通信学会コンピュテーション研究会 

     詳細を見る

    開催期間: 2019年09月02日   記述言語:日本語   開催地:岡山大学津島キャンパス  

  • Validation of NMR protein structures using rigidity theory and chemical shifts

    Kazuhito Nishiyama

    バイオ情報学研究会  情報処理学会

     詳細を見る

    開催期間: 2018年12月14日   記述言語:英語   開催地:岡山大学  

  • Max-Min 3-dispersion Problems

    Shin-ichi Nakano

    コンピュテーション研究会 

     詳細を見る

    開催期間: 2018年12月12日   記述言語:英語   開催地:東北大学  

  • パス長を限定したパスカバー問題

    小林 賢也

    若手の会セミナー2018  情報処理学会九州支部

     詳細を見る

    開催期間: 2018年12月07日 - 2018年12月08日   記述言語:日本語   開催地:国民宿舎虹ノ松原ホテル(佐賀)  

  • NMR によるタンパク質の立体構造の検証のためのFIRSTとRCIを用いた剛柔性の比較

    西山 和仁

    若手OR研究交流会2018  本オペレーションズ・リサーチ学会九州支部

     詳細を見る

    開催期間: 2018年10月27日 - 2018年10月28日   記述言語:日本語   開催地:日本文理大学湯布院研修所  

  • 三角形の個数を最大・最小にする三角分割

    江藤 宏

    コンピュテーション研究会 

     詳細を見る

    開催期間: 2018年09月18日   記述言語:日本語   開催地:九州工業大学(飯塚キャンパス)  

  • Enumeration of Nonisomorphic Interval Graphs and Nonisomorphic Permutation Graphs

    Kazuaki Yamazaki

    アルゴリズム研究会 

     詳細を見る

    開催期間: 2018年01月28日 - 2018年01月29日   記述言語:日本語   開催地:石垣島大濱信泉記念館  

  • Computational Complexity of Robot Arm Simulation Problems

    Tianfeng Feng

    アルゴリズム研究会 

     詳細を見る

    開催期間: 2018年01月28日 - 2018年01月29日   記述言語:英語   開催地:石垣島大濱信泉記念館  

  • 木における 1 ラウンドボロノイゲームの後手の最適戦略

    杉本 晃弘

    コンピュテーション研究会 

     詳細を見る

    開催期間: 2017年12月21日   記述言語:日本語   開催地:高知工科大学  

  • Circular Arc 上の独立集合を求める省領域アルゴリズム

    浦川 翔平

    コンピュテーション研究会 

     詳細を見る

    開催期間: 2017年12月21日   記述言語:日本語   開催地:高知工科大学  

  • 部分グラフクラス上での最大 k-パス頂点被覆問題

    八木田 剛

    コンピュテーション研究会 

     詳細を見る

    開催期間: 2017年12月21日   記述言語:日本語   開催地:高知工科大学  

  • 三角形総個数最大化問題

    西島 歩美

    平成29年度OR学会九州支部・若手OR交流会 

     詳細を見る

    開催期間: 2017年10月28日   記述言語:日本語   開催地:福岡工業大学FITセミナーハウス  

  • k-path vertex cover問題に関する研究

    八木田 剛

    平成29年度OR学会九州支部・若手OR交流会 

     詳細を見る

    開催期間: 2017年10月28日   記述言語:日本語   開催地:福岡工業大学FITセミナーハウス  

  • ペグソリティアとフォーティーワンの高速な解の数え上げ

    兼本 樹

    第12回 組合せゲーム・パズル研究集会 

     詳細を見る

    開催期間: 2017年03月06日   記述言語:日本語   開催地:名古屋大学  

  • 木における1ラウンドボロノイゲームの後手の戦略

    杉本 晃弘

    第12回 組合せゲーム・パズル研究集会 

     詳細を見る

    開催期間: 2017年03月06日   記述言語:日本語   開催地:名古屋大学  

  • Experimental enumeration of solutions for peg solitaire

    Ryuhei Uehara

    情報処理学会アルゴリズム研究会 

     詳細を見る

    開催期間: 2016年09月23日   記述言語:英語   開催地:徳島大学  

  • Counting the number of solutions for peg solitaire

    Itsuki Kanemoto

    コンピュテーション研究会 

     詳細を見る

    開催期間: 2016年09月06日   記述言語:英語   開催地:富山県立大学  

  • Computational Complexity of Sequential Token Swapping Problem

    Katsuhisa Yamanaka

    コンピュテーション研究会 

     詳細を見る

    開催期間: 2016年06月22日 - 2016年06月23日   記述言語:英語   開催地:石川県教育会館  

  • ゼロサプレス型二分決定グラフによる文字グラフの列挙

    斎藤 寿樹

    コンピュテーション研究会 

     詳細を見る

    開催期間: 2016年06月22日 - 2016年06月23日   記述言語:日本語   開催地:石川県教育会館  

  • Ls in L と Sphinxes in Sphinx に対する敷き詰め方の数の下界の改善 - フロンティア法による敷き詰め方の列挙 -

    兼本 樹

    コンピュテーション研究会 

     詳細を見る

    開催期間: 2016年06月22日 - 2016年06月23日   記述言語:日本語   開催地:石川県教育会館  

  • 最小重み頂点被覆問題に対する高速な発見的手法の提案

    清水 悟司

    コンピュテーション研究会 

     詳細を見る

    開催期間: 2016年04月22日   記述言語:日本語   開催地:NAIST(奈良)  

  • フロンティア法による「Ls in L」と「Sphinxes in Sphinx」の解の列挙

    兼本 樹

    第11回 組合せゲーム・パズル研究集会 

     詳細を見る

    開催期間: 2016年03月07日   記述言語:日本語   開催地:電気通信大学  

  • 手数が少ない場合におけるグリッド上のボロノイゲームの解析

    杉本 晃弘

    第11回 組合せゲーム・パズル研究集会 

     詳細を見る

    開催期間: 2016年03月07日   記述言語:日本語   開催地:電気通信大学  

  • トークン整列問題の計算複雑に関する一考察

    吉仲 亮

    アルゴリズム研究会 

     詳細を見る

    開催期間: 2016年01月21日 - 2016年01月22日   記述言語:日本語   開催地:作並温泉・湯の原ホテル(宮城)  

  • 階層グラフ描画の辺交差数削減のための道の移動処理の改良

    奥村 章平

    平成27年電気関係学会関西連合大会 

     詳細を見る

    開催期間: 2015年11月14日 - 2015年11月15日   記述言語:日本語   開催地:摂南大学  

  • 最大重みクリーク問題に対する分枝限定法に基づく近似解法に関する研究

    芝野 悟

    2015年度情報処理学会関西支部支部大会 

     詳細を見る

    開催期間: 2015年09月28日   記述言語:日本語   開催地:大阪大学  

  • Space Efficient and Output Sensitive Greedy Algorithms on Intervals

    Toshiki Saitoh

    アルゴリズム研究会 

     詳細を見る

    開催期間: 2015年09月28日   記述言語:英語   開催地:九大西新プラザ  

  • Computational Complexity of Competitive Diffusion on (Un)weighted Graphs

    Kei Uchizawa

    アルゴリズム研究会 

     詳細を見る

    開催期間: 2015年09月28日   記述言語:英語   開催地:九大西新プラザ  

  • 双方向グラフの最大重み最小帰還辺集合問題について

    荒木 徹也

    日本応用数理学会2015年度年会 

     詳細を見る

    開催期間: 2015年09月09日 - 2015年09月11日   記述言語:日本語   開催地:金沢大学  

  • 4スライダーモデルとルール処理を用いたラベル配置アルゴリズム

    寺脇 宏高

    平成26年電気関係学会関西連合大会 

     詳細を見る

    開催期間: 2014年11月24日   記述言語:日本語   開催地:NAIST(奈良)  

  • ある最大重みクリーク抽出法の前処理に関する一考察

    近藤 広樹

    平成26年電気関係学会関西連合大会 

     詳細を見る

    開催期間: 2014年11月24日   記述言語:日本語   開催地:NAIST(奈良)  

  • 分枝限定法における新たな探索法の提案

    山口 一章

    人工知能学会 第95回 人工知能基本問題研究会 

     詳細を見る

    開催期間: 2014年10月10日   記述言語:日本語   開催地:大阪大学  

  • 最小重み頂点被覆問題に対する線形時間の発見的手法の提案

    田中 智之

    情報処理学会関西支部支部大会講演論文集 

     詳細を見る

    開催期間: 2014年09月17日   記述言語:日本語   開催地:大阪大学  

  • Intersection Dimension of Bipartite Graphs

    Yota Otachi

    アルゴリズム研究会 

     詳細を見る

    開催期間: 2014年06月13日 - 2014年06月14日   記述言語:英語   開催地:道後温泉 大和屋(愛媛)  

  • グラフ上のラベル付きトークン整列問題

    山中 克久

    コンピュテーション研究会 

     詳細を見る

    開催期間: 2014年06月13日 - 2014年06月14日   記述言語:日本語   開催地:道後温泉 大和屋(愛媛)  

  • 都市における避難所割当てパターンの列挙と評価

    中野 浩太郎

    情報処理学会第76回大会 

     詳細を見る

    開催期間: 2014年03月17日   記述言語:日本語   開催地:東京電機大学  

  • 都市における避難所割当ての列挙と評価

    中野 浩太郎

    日本オペレーションズリサーチ学会 2014年春季研究発表会 

     詳細を見る

    開催期間: 2014年03月07日   記述言語:日本語   開催地:大阪大学  

  • ZDDを用いたExact Cover問題に対するパレート最適な解の列挙

    松永 涼

    アルゴリズム研究会 

     詳細を見る

    開催期間: 2014年03月03日 - 2014年03月04日   記述言語:日本語   開催地:中央大学  

  • あみだくじを数え上げる省領域アルゴリズムについて

    中嶋 章裕

    第9回 組合せゲーム・パズルミニ研究集会 

     詳細を見る

    開催期間: 2014年02月18日 - 2014年02月28日   記述言語:日本語   開催地:AIST(石川)  

  • 最大クリーク問題に対する発見的手法の高速化に関する研究

    森中 諒太

    電気関係学会関西連合大会 

     詳細を見る

    開催期間: 2013年11月16日 - 2013年11月17日   記述言語:日本語   開催地:大阪電気通信大学  

  • 階層グラフ描画における頂点順序決定アルゴリズムの提案

    的場 郁典

    電気関係学会関西連合大会 

     詳細を見る

    開催期間: 2013年11月16日 - 2013年11月17日   記述言語:日本語   開催地:大阪電気通信大学  

  • 階層グラフ描画における辺交差数を考慮したダミー頂点共有化処理

    堀尾 明久

    電気関係学会関西連合大会 

     詳細を見る

    開催期間: 2013年11月16日 - 2013年11月17日   記述言語:日本語   開催地:大阪電気通信大学  

  • 施設配置問題に対する遺伝的アルゴリズムの高速化

    岡田 諭

    電気関係学会関西連合大会 

     詳細を見る

    開催期間: 2013年11月16日 - 2013年11月17日   記述言語:日本語   開催地:大阪電気通信大学  

  • 動的計画法を用いた有向二値完全系統樹の効率のよい列挙

    斎藤 寿樹

    コンピュテーション研究会 

     詳細を見る

    開催期間: 2013年05月17日 - 2013年05月18日   記述言語:日本語   開催地:小樽商科大学  

  • 階層グラフの直交描画アルゴリズム

    荒木 徹也

    コンピュテーション研究会 

     詳細を見る

    開催期間: 2013年04月24日   記述言語:日本語   開催地: 神戸大学  

  • 動的計画法を用いた上界計算法による最大重みクリーク抽出アルゴリズムの提案

    清水 悟司

    コンピュテーション研究会 

     詳細を見る

    開催期間: 2013年03月18日   記述言語:日本語   開催地:滋賀大学  

  • Edge concentrationを 用いた交差数最小化問題に対するGAの適用

    岡田 諭

    進化計算シンポジウム2012 

     詳細を見る

    開催期間: 2012年12月15日 - 2012年12月16日   記述言語:日本語   開催地:ホテルマロウド軽井沢(長野)  

  • 部分再構築操作を組み込んだ GA による Facility Dispersion 問題の解法

    山田 光宏

    進化計算シンポジウム2012 

     詳細を見る

    開催期間: 2012年12月15日 - 2012年12月16日   記述言語:日本語   開催地:ホテルマロウド軽井沢(長野)  

  • 不完全データと矛盾しない有向二値完全系統樹を列挙する効率的手法

    岡本 吉央

    コンピュテーション研究会 

     詳細を見る

    開催期間: 2012年06月21日   記述言語:英語   開催地:北海道大学  

  • フロンティア法の計算量について

    斎藤 寿樹

    電子情報通信学会総合大会 

     詳細を見る

    開催期間: 2012年03月20日 - 2012年03月23日   記述言語:日本語   開催地:岡山大学  

  • 高速なパスの列挙アルゴリズムを用いたネットワークの信頼性評価

    斎藤 寿樹

    情報ネットワーク研究会 

     詳細を見る

    開催期間: 2011年07月21日 - 2011年07月22日   記述言語:日本語   開催地:北海道大学  

  • 等間隔の折り目を持つ紙の折り畳みの計算量について

    梅里 卓矢

    アルゴリズム研究会 

     詳細を見る

    開催期間: 2011年05月16日   記述言語:英語   開催地:秋田県立大学  

  • ZDDのリンクパズルへの応用

    吉仲 亮

    第6回 組合せゲーム・パズル ミニ研究集会 

     詳細を見る

    開催期間: 2011年03月10日   記述言語:日本語   開催地:京都大学  

  • ZDDを用いたパスの列挙とその性能評価

    斎藤 寿樹

    アルゴリズム研究会 

     詳細を見る

    開催期間: 2011年03月07日   記述言語:日本語   開催地:琉球大学  

  • Approximating the path-distance-width for k-cocomparability graphs

    Yota Otachi

    冬のLAシンポジウム 

     詳細を見る

    開催期間: 2011年01月30日 - 2011年02月01日   記述言語:英語   開催地:京都大学  

  • ZDDによるパスの列挙

    川原 純

    冬のLAシンポジウム 

     詳細を見る

    開催期間: 2011年01月30日 - 2011年02月01日   記述言語:日本語   開催地:京都大学  

  • グラフクラスと部分グラフ同型性

    斎藤 寿樹

    アルゴリズム研究会 

     詳細を見る

    開催期間: 2010年11月19日   記述言語:日本語   開催地:関西大学  

  • 幾何的特徴を持つグラフクラスに対する効率のよいアルゴリズムに関する研究

    斎藤 寿樹

    第9回情報科学技術フォーラム (FIT 2010) 

     詳細を見る

    開催期間: 2010年09月07日 - 2010年09月09日   記述言語:日本語   開催地:九州大学  

  • ラベル付き区間グラフを列挙するBDDとその応用

    斎藤 寿樹

    夏のLAシンポジウム 

     詳細を見る

    開催期間: 2010年07月20日   記述言語:日本語   開催地:九殿浜温泉ひみのはな(富山)  

  • パス上のボロノイゲーム

    清見 礼

    コンピュテーション研究会 

     詳細を見る

    開催期間: 2010年05月19日   記述言語:日本語   開催地:JAIST(石川)  

  • パス上のボロノイゲーム

    清見 礼

    第5回 組合せゲーム・パズル ミニ研究集会 

     詳細を見る

    開催期間: 2010年03月01日   記述言語:日本語   開催地:東京工業大学  

  • 二部区間グラフの効率のよい認識に関する研究

    栗林 康之

    計算機科学の理論とその応用(冬のLAシンポジウム) 

     詳細を見る

    開催期間: 2010年02月01日   記述言語:日本語   開催地:京都大学  

  • Reconstruction of Permutation Graphs and Distance Hereditary Graphs,

    斎藤 寿樹

    アルゴリズム研究会 

     詳細を見る

    開催期間: 2009年09月15日   記述言語:英語   開催地:鳥取環境大学  

  • Random Generation and Enumeration of Bipartite Permutation Graph

    斎藤 寿樹

    コンピュテーション研究会 

     詳細を見る

    開催期間: 2009年09月14日   記述言語:英語   開催地:鳥取環境大学  

  • Bipartite Permutation Graphのランダム生成と列挙

    斎藤 寿樹

    夏のLAシンポジウム 

     詳細を見る

    開催期間: 2009年07月22日 - 2009年07月24日   記述言語:日本語   開催地:かんぽの宿 松島(宮城)  

  • Reconstruction of Connected Interval Graphs

    清見 礼

    Acceleration and Visualization of Computation for Enumeration Problems 

     詳細を見る

    開催期間: 2008年09月29日 - 2008年09月30日   記述言語:英語   開催地:京都大学  

  • Proper Interval Graphsのランダム生成と列挙

    斎藤 寿樹

    夏のLAシンポジウム 

     詳細を見る

    開催期間: 2008年07月22日 - 2008年07月24日   記述言語:日本語   開催地:国民休暇村 南紀勝浦(和歌山)  

  • Simple Efficient Algorithm for MPQ-tree of an Interval Graph

    斎藤 寿樹

    コンピュテーション研究会 

     詳細を見る

    開催期間: 2007年06月29日   記述言語:日本語   開催地:北海道大学  

  • 区間表現からMPQ-treeを構築するアルゴリズム

    斎藤 寿樹

    計算機科学の理論とその応用(冬のLAシンポジウム) 

     詳細を見る

    開催期間: 2007年01月29日 - 2007年01月31日   記述言語:日本語   開催地:京都大学  

▼全件表示

講演

  • Subgraph Enumeration Algorithms by ZDDs and Its Applications

    Robotics and Computer Science  2017年09月 

     詳細を見る

    開催期間: 2017年09月08日   発表言語:英語   講演種別:特別講演   開催地:New York(the City College of New York)  

  • 区間データに対する出力サイズ依存・省領域アルゴリズム

    電気関係学会関西連合大会  2016年11月 

     詳細を見る

    開催期間: 2016年11月22日 - 2016年11月23日   発表言語:日本語   講演種別:特別講演   開催地:大阪府立大学  

学術関係受賞

  • 令和2年度OR学会九州支部・若手OR交流会 最優秀発表賞 学部生の部

    OR学会 九州支部   フロンティア法によるアルキメデスの立体の辺展開図の列挙   2020年11月28日

    塩田 拓海

     詳細を見る

    受賞国:日本国

科研費獲得実績

  • 幾何データに対する省領域アルゴリズムと時間・領域トレードオフ

    研究課題番号:16K16006  2016年04月 - 2018年03月   若手研究(B)

担当授業科目(学内)

  • 2022年度   離散アルゴリズム特論MI

  • 2022年度   離散アルゴリズム特論AI

  • 2022年度   離散アルゴリズム特論DS

  • 2022年度   計算理論

  • 2022年度   離散数学Ⅱ

  • 2022年度   離散数学Ⅰ

  • 2021年度   離散アルゴリズム特論

  • 2021年度   計算理論

  • 2021年度   離散数学Ⅱ

  • 2021年度   離散数学Ⅰ

  • 2020年度   離散アルゴリズム特論

  • 2020年度   計算理論

  • 2020年度   離散数学Ⅱ

  • 2020年度   知能情報工学実験演習Ⅱ

  • 2019年度   離散アルゴリズム特論

  • 2019年度   アルゴリズム設計S

  • 2019年度   計算理論

  • 2019年度   離散数学Ⅱ

  • 2018年度   アルゴリズム設計S

  • 2018年度   離散数学Ⅱ

  • 2018年度   離散アルゴリズム特論

  • 2017年度   アルゴリズム設計S

▼全件表示

学会・委員会等活動

  • 情報科学技術フォーラム   担当委員  

    2022年11月 - 2023年11月

  • 電子情報通信学会   英文論文誌(A)「離散数学とその応用」小特集編集委員  

    2022年08月 - 2023年09月

  • 情報処理学会   論文誌査読委員  

    2022年06月 - 2025年05月

  • 電子情報通信学会 ソサイエティ論文誌編集委員会   査読委員  

    2022年06月 - 2023年06月

  • 情報処理学会 アルゴリズム研究会研究運営委員会   幹事  

    2022年04月 - 2024年03月

  • 電子情報通信学会   英文論文誌(A)「離散数学とその応用」小特集編集委員  

    2021年08月 - 2022年09月

  • LAシンポジウム   事務局幹事  

    2021年04月 - 2022年03月

  • 電子情報通信学会   英文論文誌(A)「離散数学とその応用」小特集編集委員  

    2019年10月 - 2020年10月

  • 情報処理学会(Special Issue on the 22nd Japan Conference on Discrete and Computational Geometry, Graphs, and Games)   Guest Editor  

    2019年10月 - 2020年12月

  • The Review of Socionetwork Strategies 特集号編集委員会 (Springer)   ゲスト編集者  

    2018年09月 - 2019年10月

  • 電子情報通信学会   英文論文誌(A)「離散数学とその応用」小特集編集委員  

    2018年09月 - 2019年09月

  • 情報処理学会   論文誌ジャーナル/JIP編集委員会(基盤グループ[Computing Group])編集委員  

    2018年06月 - 2020年05月

  • 電子情報通信学会   和文論文誌 (A) 編集委員  

    2017年06月 - 2021年06月

  • 電子情報通信学会   英文論文誌 (A) 編集委員  

    2017年06月 - 2021年06月

  • 電子情報通信学会   FIT 2017 担当委員  

    2016年12月 - 2017年11月

  • 電子情報通信学会   コンピュテーション研究会 幹事  

    2016年06月 - 2018年06月

  • 情報処理学会   アルゴリズム研究会 運営委員  

    2016年04月 - 2018年04月

  • LAシンポジウム   LAシンポジウム会誌編集委員  

    2016年04月 - 2017年03月

  • 電子情報通信学会   情報システムソサイエティ誌 編集委員  

    2012年04月 - 2014年03月

▼全件表示

国際交流窓口担当

  • 国際情報処理科学院  フランス共和国  2018年04月 - 現在