研究者業績

清見 礼

キヨミ マサシ  (Masashi Kiyomi)

基本情報

所属
成蹊大学 理工学部 理工学科 教授
学位
博士(情報学)(総合研究大学院大学)

J-GLOBAL ID
201201001276504150
researchmap会員ID
7000002258

- 2006年情報処理学会コンピュータサイエンス領域奨励賞
- IEEE ICDM Workshop on Frequent Itemset Mining Implementations, 2004, Best Implementation Award

研究キーワード

 2

論文

 49
  • Yuuki Aoike, Masashi Kiyomi, Yasuaki Kobayashi, Yota Otachi
    IEICE Trans. Inf. Syst. 107(4) 559-563 2024年  査読有り
  • Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Kazuhiro Kurita, Yota Otachi
    AAAI 3968-3976 2023年  査読有り
  • Yuuki Aoike, Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Kazuhiro Kurita, Yota Otachi
    Theory Comput. Syst. 66(2) 502-515 2022年  査読有り
  • Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yota Otachi
    Theor. Comput. Sci. 918 60-76 2022年  査読有り
  • Rémy Belmonte, Tesshu Hanaka, Masaaki Kanzaki, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi 0001, Michael Lampis, Hirotaka Ono, Yota Otachi
    Algorithmica 84(4) 871-895 2022年  査読有り
  • Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yota Otachi
    Lecture Notes in Computer Science 12701 271-285 2021年  査読有り
  • Masashi Kiyomi, Takashi Horiyama, Yota Otachi
    Inf. Process. Lett. 168 106084-106084 2021年  査読有り
  • Kazuaki Yamazaki, Toshiki Saitoh, Masashi Kiyomi, Ryuhei Uehara
    Theoretical Computer Science 806 310-322 2020年2月  査読有り
  • Masashi Kiyomi, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui
    Theory Comput. Syst. 64(3) 522-541 2020年  査読有り
  • Rémy Belmonte, Tesshu Hanaka, Masaaki Kanzaki, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Michael Lampis, Hirotaka Ono, Yota Otachi
    Lecture Notes in Computer Science 12126 43-55 2020年  査読有り
  • Bireswar Das,Murali, Krishna Enduri, Masashi Kiyomi, Neeldhara Misra, Yota Otachi, I. Vinod Reddy, Shunya Yoshimura
    Theor. Comput. Sci. 782 79-90 2019年  査読有り
  • Rémy Belmonte, Mehdi Khosravian Ghadikolaei, Masashi Kiyomi, Michael Lampis, Yota Otachi
    J. Graph Algorithms Appl. 23(2) 111-134 2019年  査読有り
  • Rémy Belmonte, Mehdi Khosravian Ghadikolaei, Masashi Kiyomi, Michael Lampis, Yota Otachi
    Leibniz International Proceedings in Informatics, LIPIcs 100 51-513 2018年6月1日  査読有り
    FIXED-FLOOD-IT and FREE-FLOOD-IT are combinatorial problems on graphs that generalize a very popular puzzle called Flood-It. Both problems consist of recoloring moves whose goal is to produce a monochromatic ("flooded") graph as quickly as possible. Their difference is that in FREE-FLOOD-IT the player has the additional freedom of choosing the vertex to play in each move. In this paper, we investigate how this freedom affects the complexity of the problem. It turns out that the freedom is bad in some sense. We show that some cases trivially solvable for FIXED-FLOOD-IT become intractable for FREE-FLOOD-IT. We also show that some tractable cases for FIXED-FLOOD-IT are still tractable for FREE-FLOOD-IT but need considerably more involved arguments. We finally present some combinatorial properties connecting or separating the two problems. In particular, we show that the length of an optimal solution for FIXED-FLOOD-IT is always at most twice that of FREE-FLOOD-IT, and this is tight.
  • Kazuaki Yamazaki, Toshiki Saitoh, Masashi Kiyomi, Ryuhei Uehara
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 10755 8-19 2018年  査読有り
    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.
  • Masashi Kiyomi, Hirotaka Ono,Array, Pascal Schweitzer, Jun Tarui
    35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France 44:1-44:15 2018年  査読有り
  • Masashi Kiyomi, Yota Otachi
    DISCRETE APPLIED MATHEMATICS 223 91-97 2017年5月  査読有り
    An alliance in a graph is a set of vertices that is either safe under attacks from the neighborhood (defensive), capable of attacking its neighbors (offensive), or simultaneously defensive and offensive (powerful). An alliance is global if all nonmembers are adjacent to some members of the alliance. The concept of alliances was introduced by Kristiansen et al. (2004). After that many results concerning the complexity for finding a minimum alliance were shown. It was shown that the problem of finding a minimum alliance of any variant is NP-hard in general. For some variants, it was shown that the problem becomes polynomial time solvable when restricted to trees or series-parallel graphs. In this paper, we show that the problems for all variants are efficiently solvable for much larger graph classes. We present a polynomial-time algorithm for graphs of bounded clique-width. We also show that the problem is fixed-parameter tractable when parameterized by the vertex cover number. (C) 2017 Elsevier B.V. All rights reserved.
  • Takashi Horiyama, Masashi Kiyomi, Yoshio Okamoto, Ryuhei Uehara, Takeaki Uno, Yushi Uno, Yukiko Yamauchi
    Journal of Information Processing 25(8) 708-715 2017年  査読有り
    We study a combinatorial game named "sankaku-tori" in Japanese, which means "triangle-taking" in English. It is an old pencil-and-paper game for two players played in Western Japan. The game is played on points on the plane in general position. In each turn, a player adds a line segment to join two points, and the game ends when a triangulation of the point set is completed. The player who completes more triangles than the other wins. In this paper, we formalize this game and investigate three restricted variants of this game. We first investigate a solitaire variant; for a given set of points and line segments with two integers t and k, the problem asks if you can obtain t triangles after k moves. We show that this variant is NP-complete in general. The second variant is the standard two player version, but the points are in convex position. In this case, the first player has a nontrivial winning strategy. The last variant is a natural extension of the second one; we have the points in convex position but one point inside. Then, it turns out that the first player has no winning strategy.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.25(2017) (online)DOI http://dx.doi.org/10.2197/ipsjjip.25.708------------------------------We study a combinatorial game named "sankaku-tori" in Japanese, which means "triangle-taking" in English. It is an old pencil-and-paper game for two players played in Western Japan. The game is played on points on the plane in general position. In each turn, a player adds a line segment to join two points, and the game ends when a triangulation of the point set is completed. The player who completes more triangles than the other wins. In this paper, we formalize this game and investigate three restricted variants of this game. We first investigate a solitaire variant; for a given set of points and line segments with two integers t and k, the problem asks if you can obtain t triangles after k moves. We show that this variant is NP-complete in general. The second variant is the standard two player version, but the points are in convex position. In this case, the first player has a nontrivial winning strategy. The last variant is a natural extension of the second one; we have the points in convex position but one point inside. Then, it turns out that the first player has no winning strategy.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.25(2017) (online)DOI http://dx.doi.org/10.2197/ipsjjip.25.708------------------------------
  • Akira Suzuki, Masashi Kiyomi, Yota Otachi, Kei Uchizawa, Takeaki Uno
    Journal of Information Processing 25(8) 695-707 2017年  査読有り
    Hitori is a popular "pencil-and-paper" puzzle defined as follows. In n-hitori, we are given an n × n rectangular grid in which each square is labeled with a positive integer, and the goal is to paint a subset of the squares so that the following three rules are satisfied: Rule 1) No row or column has a repeated unpainted label; Rule 2) Painted squares are never (horizontally or vertically) adjacent; Rule 3) The unpainted squares are all connected (via horizontal and vertical connections). The grid is called an instance of n-hitori if it has a unique solution. In this paper, we introduce hitori number and maximum hitori numberwhich are defined as follows: For every integer n, hitori number h(n) is the minimum number of different integers used in an instance where the minimum is taken over all the instances of n-hitori. For every integer n, maximum hitori number $\bar{h}(n)$ is the maximum number of different integers used in an instance where the maximum is taken over all the instances of n-hitori. We then prove that ⎾(2n-1)/3⏋ ≤ h(n) ≤ 2⎾n/3⏋+1 for n ≥ 2 and ⎾(4n2-4n+11)/5⏋ ≤ $\bar{h}(n)$ ≤ (4n2+2n-2)/5 for n ≥ 3.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.25(2017) (online)DOI http://dx.doi.org/10.2197/ipsjjip.25.695------------------------------Hitori is a popular "pencil-and-paper" puzzle defined as follows. In n-hitori, we are given an n × n rectangular grid in which each square is labeled with a positive integer, and the goal is to paint a subset of the squares so that the following three rules are satisfied: Rule 1) No row or column has a repeated unpainted label; Rule 2) Painted squares are never (horizontally or vertically) adjacent; Rule 3) The unpainted squares are all connected (via horizontal and vertical connections). The grid is called an instance of n-hitori if it has a unique solution. In this paper, we introduce hitori number and maximum hitori numberwhich are defined as follows: For every integer n, hitori number h(n) is the minimum number of different integers used in an instance where the minimum is taken over all the instances of n-hitori. For every integer n, maximum hitori number $\bar{h}(n)$ is the maximum number of different integers used in an instance where the maximum is taken over all the instances of n-hitori. We then prove that ⎾(2n-1)/3⏋ ≤ h(n) ≤ 2⎾n/3⏋+1 for n ≥ 2 and ⎾(4n2-4n+11)/5⏋ ≤ $\bar{h}(n)$ ≤ (4n2+2n-2)/5 for n ≥ 3.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.25(2017) (online)DOI http://dx.doi.org/10.2197/ipsjjip.25.695------------------------------
  • Masashi Kiyomi, Yota Otachi
    INFORMATION PROCESSING LETTERS 116(9) 569-573 2016年9月  査読有り
    We present a polynomial-time algorithm for solving SUBGRAPH ISOMORPHISM where the base graphs are bipartite permutation graphs and the pattern graphs are chain graphs. (C) 2016 Elsevier B.V. All rights reserved.
  • Ei Ando, Akitoshi Kawamura, Masashi Kiyomi, Eiji Miyano, Hirotaka Ono
    Proceedings of 19th Japan-Korean Joint Workshop on Algorithms and Computation (WAAC2016) 71-1-71-4 2016年8月30日  
  • Masashi Kiyomi
    Encyclopedia of Algorithms 2016 1840-1842 2016年  招待有り
  • Masashi Kiyomi, Yoshio Okamoto, Yota Otachi
    DISCRETE APPLIED MATHEMATICS 198 303-306 2016年1月  査読有り
    Many graph parameters of grid-like graphs are studied because of their algorithmic consequences. An important concept in this context is that of treewidth. Treewidth of graphs is a graph parameter for measuring how close a graph is to a tree. In this paper, we study the treewidth of toroidal grids and show that the treewidth of the n x n toroidal grid is either 2n - 2 or 2n - 1. We then show that these bounds are tight in some cases. To show the lower bounds, we construct brambles of high orders. (C) 2015 Elsevier B.V. All rights reserved.
  • Katsuhisa Yamanaka, Erik D. Demaine, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, Takeaki Uno
    THEORETICAL COMPUTER SCIENCE 586 81-94 2015年6月  査読有り
    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 alpha-approximation algorithm for graphs whose tree a-spanners can be computed in polynomial time. Finally, we show that the problem can be solved exactly in polynomial time on complete bipartite graphs. (C) 2015 Elsevier B.V. All rights reserved.
  • Tetsuo Asano, Taisuke Izumi, Masashi Kiyomi, Matsuo Konagaya, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui, Ryuhei Uehara
    ALGORITHMS AND COMPUTATION, ISAAC 2014 8889 553-564 2014年  査読有り
    We provide algorithms performing Depth-First Search (DFS) on a directed or undirected graph with n vertices and m edges using only O(n) bits. One algorithm uses O(n) bits and runs in O(mlog n) time. Another algorithm uses n+ o(n) bits and runs in polynomial time. Furthermore, we show that DFS on a directed acyclic graph can be done in space n/2(Omega(root log n)) and in polynomial time, and we also give a simple linear-time O(log n)-space algorithm for the depth-first traversal of an undirected tree. Finally, we also show that for a graph having an O(1)-size feedback set, DFS can be done in O(log n) space. Our algorithms are based on the analysis of properties of DFS and applications of the s-t connectivity algorithms due to Reingold and Barnes et al., both of which run in sublinear space.
  • Katsuhisa Yamanaka, Erik D. Demaine, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, Takeaki Uno
    FUN WITH ALGORITHMS 8496 364-375 2014年  査読有り
    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 alpha-approximation algorithm for graphs whose tree a-spanners can be computed in polynomial time. Finally, we show that the problem can be solved exactly in polynomial time on complete bipartite graphs.
  • Takashi Horiyama, Masashi Kiyomi, Yoshio Okamoto, Ryuhei Uehara, Takeaki Uno, Yushi Uno, Yukiko Yamauchi
    FUN WITH ALGORITHMS 8496 230-239 2014年  査読有り
    We study a combinatorial game named "sankaku-tori" in Japanese, which means "triangle-taking" in English. It is an old pencil-and-paper game for two players played in Western Japan. The game is played on points on the plane in general position. In each turn, a player adds a line segment to join two points, and the game ends when a triangulation of the point set is completed. The player who completes more triangles than the other wins. In this paper, we consider two restricted variants of this game. In the first variant, the first player always wins in a nontrivial way, and the second variant is NP-complete in general.
  • Masashi Kiyomi, Toshiki Saitoh, Ryuhei Uehara
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS E96D(3) 426-432 2013年3月  査読有り
    PREMAGE 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.
  • Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7276 248-259 2012年  査読有り
    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&amp 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&amp 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.
  • Masashi Kiyomi, Toshiki Saitoh, Ryuhei Uehara
    Discrete Math., Alg. and Appl. 4(3) 1250039-1250039 2012年  査読有り
    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.
  • Masashi Kiyomi, Toshiki Saitoh, Ryuhei Uehara
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS E94D(6) 1185-1189 2011年6月  査読有り
    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 I-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.
  • Jean Cardinal, Erik D. Demaine, Martin L. Demaine, Shinji Imahori, Tsuyoshi Ito, Masashi Kiyomi, Stefan Langerman, Ryuhei Uehara, Takeaki Uno
    GRAPHS AND COMBINATORICS 27(3) 341-351 2011年5月  査読有り
    How do we most quickly fold a paper strip (modeled as a line) to obtain a desired mountain-valley pattern of equidistant creases (viewed as a binary string)? Define the folding complexity of a mountain-valley string as the minimum number of simple folds required to construct it. We first show that the folding complexity of a length-n uniform string (all mountains or all valleys), and hence of a length-n pleat (alternating mountain/valley), is O(lg(2) n). We also show that a lower bound of the complexity of the problems is Omega(lg(2) n/lg lg n). Next we show that almost all mountain-valley patterns require Omega(n/lg n) folds, which means that the uniform and pleat foldings are relatively easy problems. We also give a general algorithm for folding an arbitrary sequence of length n in O(n/lg n) folds, meeting the lower bound up to a constant factor.
  • Yosuke Okayama, Masashi Kiyomi, Ryuhei Uehara
    Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, Toronto, Ontario, Canada, August 10-12, 2011 2011年  査読有り
  • Masashi Kiyomi, Toshiki Saitoh, Ryuhei Uehara
    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. (C) 2010 Elsevier B.V. All rights reserved.
  • Toshiki Saitoh, Katsuhisa Yamanaka, Masashi Kiyomi, Ryuhei Uehara
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS E93D(7) 1816-1823 2010年7月  査読有り
    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.
  • Shuji Kijima, Masashi Kiyomi, Yoshio Okamoto, Takeaki Uno
    THEORETICAL COMPUTER SCIENCE 411(26-28) 2591-2601 2010年6月  査読有り
    We discuss the problems to list, sample, and count the chordal graphs with edge constraints. The objects we look at are chordal graphs sandwiched by a given pair of graphs where we assume that at least one of the input graphs is chordal. The setting is a natural generalization of chordal completions and deletions. For the listing problem, we give an efficient algorithm running in polynomial time per output with polynomial space. As for the sampling problem, we give two clues that indicate that a random sampling is not easy. The first clue is that we show #P-completeness results for counting problems. The second clue is that we give an instance for which a natural Markov chain suffers from an exponential mixing time. These results provide a unified viewpoint from algorithms' theory to problems arising from various areas such as statistics, data mining, and numerical computation. (C) 2010 Elsevier B.V. All rights reserved.
  • Masashi Kiyomi, Toshiki Saitoh, Ryuhei Uehara
    WALCOM: ALGORITHMS AND COMPUTATION, PROCEEDINGS 5942 125-135 2010年  査読有り
    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 time 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.
  • Masashi Kiyomi, Toshiki Saitoh, Ryuhei Uehara
    COMBINATORIAL OPTIMIZATION AND APPLICATIONS, PT II 6509 362-+ 2010年  査読有り
    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.
  • Ondrej Bílka, Kevin Buchin, Radoslav Fulek, Masashi Kiyomi, Yoshio Okamoto, Shin-ichi Tanigawa, Csaba D. Tóth
    Electr. J. Comb. 17(1) 2010年  査読有り
  • Toshiki Saitoh, Katsuhisa Yamanaka, Masashi Kiyomi, Ryuhei Uehara
    WALCOM: ALGORITHMS AND COMPUTATION, PROCEEDINGS 5431 177-+ 2009年  査読有り
    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.
  • Masashi Kiyomi, Toshiki Saitoh, Ryuhei Uehara
    COMPUTING AND COMBINATORICS, PROCEEDINGS 5609 106-115 2009年  査読有り
    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, PREIMACE CONSTRUCTION, and PREIMAGE COUNTING on interval graphs is not trivial. We present that these three problems are solvable in polynomial time on interval graphs.
  • Shuji Kijima, Masashi Kiyomi, Yoshio Okamoto, Takeaki Uno
    COMPUTING AND COMBINATORICS, PROCEEDINGS 5092 458-+ 2008年  査読有り
    We discuss the problems to list, sample, and count the chordal graphs with edge constraints. The objects we look at are chordal graphs sandwiched by a given pair of graphs where we assume at least one of the input pair is chordal. The setting is a natural generalization of chordal completions and deletions. For the listing problem, we give an efficient algorithm running in polynomial time per output with polynomial space. As for the sampling problem, we give two clues that seem to imply that a random sampling is not easy. The first clue is that we show #P-completeness results for counting problems. The second clue is that we give an instance for which a natural Markov chain suffers from an exponential mixing time. These results provide a unified viewpoint from algorithms theory to problems arising from various areas such as statistics, data mining, and numerical computation.
  • Toshiki Saitoh, Masashi Kiyomi, Ryuhei Uehara
    Proceedings of the KOREA-JAPAN Joint Workshop on Algorithms and Computation (WAAC 2007) 121-126 2007年  
  • M Kiyomi, T Uno
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS E89D(2) 763-770 2006年2月  査読有り
    A chordal graph is a graph which contains no chordless cycle of at least four edges as an induced subgraph. The class of chordal graphs contains many famous graph classes such as trees, interval graphs, and split graphs, and is also a subclass of perfect graphs. In this paper, we address the problem of enumerating all labeled chordal graphs included in a given graph. We think of some variations of this problem. First we introduce an algorithm to enumerate all connected labeled chordal graphs in a complete graph of n vertices. Next, we extend the algorithm to an algorithm to enumerate all labeled chordal graphs in a n-vertices complete graph. Then, we show that we can use, with small changes, these algorithms to generate all (connected or not necessarily connected) labeled chordal graphs in arbitrary graph. All our algorithms are based on reverse search method, and time complexities to generate a chordal graph are O(l), and also O(l) delay. Additionally, we present an algorithm to generate every clique of a given chordal graph in constant time. Using these algorithms we obtain combinatorial Gray code like sequences for these graph structures in which the differences between two consecutive graphs are bounded by a constant size.
  • Masashi Kiyomi, Shuji Kijima, Takeaki Uno
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE 4271 68-77 2006年  査読有り
    We propose three algorithms for enumeration problems; given a graph G, to find every chordal supergraph (in K-n) of G, to find every interval supergraph (in K.) of G, and to find every interval subgraph of G in K-n. The algorithms are based on the reverse search method. A graph is chordal if and only if it has no induced chordless cycle of length more than three. A graph is an interval graph if and only if it has an interval representation. To the best of our knowledge, ours are the first results about the enumeration problems to list every interval subgraph of the input graph and to list every chordal/interval supergraph of the input graph in polynomial time. The time complexities of the first algorithm is O((n + m)(2)) for each output graph, and those for the rest two algorithms are O(n(3)) for each output graph, where m is the number of edges of input graph G. We also show that a straight-forward depth-first search type algorithm is not appropriate for these problems.
  • Takeaki Uno, Masashi Kiyomi, Hiroki Arimura
    Open Source Data Mining Workshop on Frequent Pattern Mining Implementations 2005 2005年8月  査読有り
  • Masashi Kiyomi, Takeaki Uno, Tomomi Matsui
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 3828 602-611 2005年  査読有り
    We present two efficient algorithms for solving the electric power transaction problem. The electric power transaction problem appears when maximizing the social benefit on electric power transactions among some private companies. The problem is a special case of the minimum cost flow problem defined on a network with many leaves, where each leaf corresponds to a (private) company who wants to sell or buy electric power. Our first algorithm is based on the minimum mean cycle canceling algorithm and the second algorithm uses a linear time median finding algo-rithm. The first algorithm finds an optimal solution in O(n log n k5 log (kC)) time where n is the number of leaves, k is the number of non-leaf vertices and C is the highest electric power price per unit that companies may offer. The time complexity of the second algorithm is bounded by O((n + k3)2kk!) time, which is linear in n. In many practical instances, k is small and n is very large, hence these algorithms solve the problem more efficiently than the ordinary network flow algorithms. © Springer-Verlag Berlin Heidelberg 2005.
  • Timothy Furtak, Masashi Kiyomi, Takeaki Uno, Michael Buro
    19TH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE (IJCAI-05) 132-137 2005年  査読有り
    Amazons is a perfect information board game with simple rules and large branching factors. Two players alternately move chess queen-like pieces and block squares on a 10 x 10 playing field. The player who makes the last move wins. Amazons endgames usually decompose into independent subgames. Therefore, the game is a natural testbed for combinatorial game theory. It was known that determining the winner of simple generalized Amazons endgames is NP-equivalent. This paper presents two proofs for the PSPACE-completeness of the generalized version of the full game.
  • Takeaki Uno, Masashi Kiyomi, Hiroki Arimura
    FIMI '04, Proceedings of the IEEE ICDM Workshop on Frequent Itemset Mining Implementations, Brighton, UK, November 1, 2004 2004年  査読有り
  • Masashi Kiyomi, Tomomi Matsui
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 2063 229-240 2001年  査読有り
    Peg solitaire is a one player game using pegs and a board with some holes. The game is classical, and nowadays sold in many parts of the world under the trade name of Hi-Q. In this paper, we dealt with the peg solitaire problem as an integer programming problem. We proposed algorithms based on the backtrack search method and relaxation methods for integer programming problem. The algorithms first solve relaxed problems and get an upper bound of the number of jumps for each jump position. This upper bound saves much time at the next stage of backtrack searching. While solving the relaxed problems, we can prove many peg solitaire problems are infeasible. We proposed two types of backtrack searching, forward-only searching and forward-backward searching. The performance of these two methods highly depends on the symmetricity and the length of the sequence of required jumps. Our algorithm can solve all the peg solitaire problem instances we tried and the total computational time is less than 20 minutes on an ordinary notebook personal computer.

MISC

 23

書籍等出版物

 1
  • 清見 礼 (担当:分担執筆, 範囲:特集= 大学数学のキーポイント(前篇)アルゴリズム/情報数学の一例として pp.37-41)
    2019年3月

共同研究・競争的資金等の研究課題

 2