研究者詳細 - 斎藤　寿樹

論文 - 斎藤　寿樹

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

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

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

Discrete Applied Mathematics 168 69 - 77 2014年05月

記述言語：英語掲載種別：研究論文（学術雑誌）

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

DOI： 10.1016/j.dam.2012.11.015

Scopus

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

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

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

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

Swapping labeled tokens on graphs 査読有り

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

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

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

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

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

Scopus

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

Intersection dimension of bipartite graphs 査読有り

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

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

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

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

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

Scopus

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

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

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

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

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

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

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

Scopus

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

The complexity of the stamp folding problem 査読有り

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

Theoretical Computer Science 497 13 - 19 2013年07月

記述言語：英語掲載種別：研究論文（学術雑誌）

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

DOI： 10.1016/j.tcs.2012.08.006

Scopus

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

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

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

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

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

Kiyomi M., Saitoh T., Uehara R.

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

記述言語：英語掲載種別：研究論文（学術雑誌）

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

DOI： 10.1587/transinf.E96.D.426

Scopus

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

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

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

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

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

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

Scopus

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

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

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

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

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

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

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

Subgraph isomorphism in graph classes 査読有り

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

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

記述言語：英語掲載種別：研究論文（学術雑誌）

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

DOI： 10.1016/j.disc.2012.07.010

Scopus

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

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

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

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

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

Kiyomi M., Okamoto Y., Saitoh T.

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

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

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

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

Scopus

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

Bipartite Permutation Graphs are Reconstructible 査読有り

Masashi Kiyomi, Toshiki Saitoh, and Ryuhei Uehara

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

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

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

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

記述言語：英語掲載種別：研究論文（学術雑誌）

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

DOI： 10.3390/a5020176

Scopus

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

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

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

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

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

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

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

記述言語：英語掲載種別：研究論文（学術雑誌）

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

DOI： 10.1016/j.jda.2011.11.001

Scopus

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

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

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

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

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

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

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

Scopus

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

Complexity of the stamp folding problem 査読有り

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

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

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

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

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

Scopus

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

　前のページ - 次のページ　

<斎藤 寿樹>

論文 - 斎藤 寿樹

<斎藤　寿樹>

論文 - 斎藤　寿樹