研究者詳細 - 斎藤　寿樹

論文 - 斎藤　寿樹

分割表示 >> ／全件表示73 件中 1 - 73 件目

Efficient non-isomorphic graph enumeration algorithms for several intersection graph classes 招待有り査読有り国際誌

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

Theoretical Computer Science 1003 2024年07月

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

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 O(n)-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 so that it enumerates those with constraints on the maximum (bi)clique size and/or the number of edges.

DOI： 10.1016/j.tcs.2024.114591

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

Overlapping edge unfoldings for convex regular-faced polyhedra 招待有り査読有り国際誌

Shiota T., Saitoh T.

Theoretical Computer Science 1002 2024年06月

担当区分：最終著者記述言語：英語掲載種別：研究論文（学術雑誌）

Herein, we discuss the existence of overlapping edge unfoldings for convex regular-faced polyhedra. Horiyama and Shoji showed that there are no overlapping edge unfoldings for all platonic solids and five of the Archimedean solids. The remaining five Archimedean solids were 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 (3≤n≤23), an m-gonal Archimedean antiprism (3≤m≤11), and 48 types of Johnson solids do not overlap. Our algorithm finds overlapping edge unfoldings for the snub cube, and 44 types of Johnson solids. We present analytic proof that an overlapping edge unfolding exists in an n-gonal Archimedean prism (n≥24), and an m-gonal Archimedean antiprism (m≥12). Our results prove the existence of overlapping edge unfoldings for convex regular-faced polyhedra.

DOI： 10.1016/j.tcs.2024.114593

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

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

その他リンク： 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

その他リンク： 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

その他リンク： 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

その他リンク： 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

その他リンク： 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日

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∪ { + ∞, - ∞}, which defines a weight for each path in its length, 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 especially consider MinPLPC with 0–1 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. That is, MaxPLPC is to maximize the number of vertices contained in the paths with length ℓ∈ L in a path cover. In this paper, we first show that MinP{ 0, 1, 2 }PC is NP-hard for planar bipartite graphs of maximum degree three. This implies that (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, (iii) we present a polynomial-time algorithm for MinP{0,1,⋯,k}PC on graphs with bounded treewidth for a fixed k. Lastly, (iv) we present a 4-approximation algorithm for MaxP{3,⋯,n-1}PC, which becomes a 2.5-approximation for subcubic graphs.

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

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

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

その他リンク： 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

その他リンク： 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

その他リンク： 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

その他リンク： 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

その他リンク： 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

その他リンク： 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月

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

その他リンク： 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

その他リンク： 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

その他リンク： 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

その他リンク： 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

その他リンク： 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

その他リンク： 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

その他リンク： 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.

その他リンク： 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

その他リンク： 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

その他リンク： 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

その他リンク： 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

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84931067125&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

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85014234196&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

その他リンク： 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

その他リンク： 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

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85014285826&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

その他リンク： 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

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

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

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

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

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

その他リンク： 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

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84930241571&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

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

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

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

電子情報通信学会論文誌 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月

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

その他リンク： 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

その他リンク： 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

その他リンク： 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

その他リンク： 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

その他リンク： 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

その他リンク： 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.

その他リンク： 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月

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

その他リンク： 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

その他リンク： 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月

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

その他リンク： 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

その他リンク： 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

その他リンク： 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

その他リンク： 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月

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

その他リンク： 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

その他リンク： 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

その他リンク： 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月

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

その他リンク： 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

その他リンク： 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月

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

その他リンク： 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

その他リンク： 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

その他リンク： 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月

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月

　前のページ-次のページ　

1