研究者詳細 - 斎藤　寿樹

論文 - 斎藤　寿樹

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

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

Scopus

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

Bipartite permutation graphs are reconstructible 査読有り

Kiyomi M., Saitoh T., Uehara R.

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

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

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

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

Scopus

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

Reconstruction of interval graphs 査読有り

Kiyomi M., Saitoh T., Uehara R.

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

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

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

DOI： 10.1016/j.tcs.2010.07.006

Scopus

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

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

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

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

Reconstruction algorithm for permutation graphs 査読有り

Kiyomi M., Saitoh T., Uehara R.

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

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

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

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

Scopus

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

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

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

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

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

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

DOI： 10.1587/transinf.E93.D.1816

Scopus

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

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

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

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

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

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

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

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

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

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

Scopus

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

Reconstruction of interval graphs 査読有り

Kiyomi M., Saitoh T., Uehara R.

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

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

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

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

Scopus

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

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

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

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

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

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

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

Scopus

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

Reconstruction of Interval Graphs 査読有り

Masashi Kiyomi, Toshiki Saitoh, and Ryuhei Uehara

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

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月

　前のページ -次のページ　

<斎藤 寿樹>

論文 - 斎藤 寿樹

<斎藤　寿樹>

論文 - 斎藤　寿樹