研究者詳細 - 大舘　陽太

論文 - 大舘　陽太

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

Combined graph kernels for automatic patent classification: A hybrid approach 査読有り

Budi Nugroho, Masayoshi Aritsugi, Yota Otachi, Yuki Manabe

World Patent Information 57 巻頁： 18 - 24 2019年6月

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

© 2019 Elsevier Ltd In this study, we proposed combined kernel-based methods to leverage patent citation graph performance for patent classification. The concept is to use the combined graph kernels of the citation graph to classify patent documents, as a hybrid approach. A multiple kernel framework was used for integrating multiple datasets of various kernels into a combined kernel. We employed seven graph kernels as the baselines and the combination of random walks and Weisfeiler–Lehman subtree kernels to achieve higher performance. We calculated the kernel values of each patent pairwise and employed an SVM classifier to carry out the classification task. The investigation results demonstrate that the combined graph kernel outperforms single kernels.

DOI： 10.1016/j.wpi.2019.03.002

Scopus

researchmap

Subgraph Isomorphism on Graph Classes that Exclude a Substructure. 査読有り国際共著

Hans L. Bodlaender, Tesshu Hanaka, Yoshio Okamoto, Yota Otachi, Tom C. van, der Zanden

Algorithms and Complexity - 11th International Conference, CIAC 2019, Rome, Italy, May 27-29, 2019, Proceedings 11485 巻頁： 87 - 98 2019年

Independent Set Reconfiguration Parameterized by Modular-Width. 査読有り国際共著

Belmonte, Tesshu Hanaka, Michael Lampis, Hirotaka Ono, Yota Otachi

Graph-Theoretic Concepts in Computer Science - 45th International Workshop, WG 2019, Vall de Núria, Spain, June 19-21, 2019, Revised Papers 11789 巻頁： 285 - 297 2019年

Low-Congestion Shortcut and Graph Parameters. 査読有り

Naoki Kitamura, Hirotaka Kitagawa, Yota Otachi, Taisuke Izumi

Leibniz International Proceedings in Informatics 146 巻頁： 25:1-25:17 2019年

Parameterized Complexity of Safe Set. 査読有り国際共著

Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Hirotaka Ono, Yota Otachi

Algorithms and Complexity - 11th International Conference, CIAC 2019, Rome, Italy, May 27-29, 2019, Proceedings 11485 巻頁： 38 - 49 2019年

How Bad is the Freedom to Flood-It? 査読有り国際共著

Rémy Belmonte, Mehdi Khosravian Ghadikolaei, Masashi Kiyomi, Michael Lampis, Yota Otachi

J. Graph Algorithms Appl. 23 巻 ( 2 ) 頁： 111 - 134 2019年

A lower bound on opaque sets. 査読有り国際共著

Akitoshi Kawamura, Sonoko Moriyama, Yota Otachi, János Pach

Comput. Geom. 80 巻頁： 13 - 22 2019年

On the Classes of Interval Graphs of Limited Nesting and Count of Lengths. 査読有り国際共著

Pavel Klavík, Yota Otachi, Jirí Sejnoha

Algorithmica 81 巻 ( 4 ) 頁： 1490 - 1511 2019年

On structural parameterizations of firefighting. 査読有り国際共著

Bireswar Das, Murali Krishna Enduri, Masashi Kiyomi, Neeldhara Misra, Yota Otachi, I. Vinod Reddy, Shunya Yoshimura

Theor. Comput. Sci. 782 巻頁： 79 - 90 2019年

On Computational Complexity of Pipe Puzzles 査読有り

SHIRAYAMA Takumu, SHIGEMURA Takuto, OTACHI Yota, MIYAZAKI Shuichi, UEHARA Ryuhei

IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 102 巻 ( 9 ) 頁： 1134 - 1141 2019年

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：一般社団法人電子情報通信学会

<p>In this paper, we investigate computational complexity of pipe puzzles. A pipe puzzle is a kind of tiling puzzle; the input is a set of cards, and a part of a pipe is drawn on each card. For a given set of cards, we arrange them and connect the pipes. We have to connect all pipes without creating any local loop. While ordinary tiling puzzles, like jigsaw puzzles, ask to arrange the tiles with local consistency, pipe puzzles ask to join all pipes. We first show that the pipe puzzle is NP-complete in general even if the goal shape is quite restricted. We also investigate restricted cases and show some polynomial-time algorithms.</p>

DOI： 10.1587/transfun.E102.A.1134

Reconfiguration of colorable sets in classes of perfect graphs. 査読有り

Takehiro Ito, Yota Otachi

Theor. Comput. Sci. 772 巻頁： 111 - 122 2019年

Token Sliding on Split Graphs. 査読有り国際共著

Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi, Florian Sikora

Leibniz International Proceedings in Informatics 126 巻頁： 13:1-13:17 2019年

Degree-Constrained Orientation of Maximum Satisfaction: Graph Classes and Parameterized Complexity 査読有り国際共著

Hans L. Bodlaender, Hirotaka Ono, Yota Otachi

Algorithmica 80 巻 ( 7 ) 頁： 2160 - 2180 2018年7月

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：Springer New York LLC

The problem MaxW-Light (MaxW-Heavy) for an undirected graph is to assign a direction to each edge so that the number of vertices of outdegree at most W (resp. at least W) is maximized. It is known that these problems are NP-hard even for fixed W. For example, Max 0-Light is equivalent to the problem of finding a maximum independent set. In this paper, we show that for any fixed constant W, MaxW-Heavy can be solved in linear time for hereditary graph classes for which treewidth is bounded by a function of degeneracy. We show that such graph classes include chordal graphs, circular-arc graphs, d-trapezoid graphs, chordal bipartite graphs, and graphs of bounded clique-width. To have a polynomial-time algorithm for MaxW-Light, we need an additional condition of a polynomial upper bound on the number of potential maximal cliques to apply the metatheorem by Fomin et al. (SIAM J Comput 44:54–87, 2015). The aforementioned graph classes, except bounded clique-width graphs, satisfy such a condition. For graphs of bounded clique-width, we present a dynamic programming approach not using the metatheorem to show that it is actually polynomial-time solvable for this graph class too. We also study the parameterized complexity of the problems and show some tractability and intractability results.

DOI： 10.1007/s00453-017-0399-9

Scopus

researchmap

Swapping colored tokens on graphs 査読有り国際共著

Katsuhisa Yamanaka, Takashi Horiyama, J. Mark Keil, David Kirkpatrick, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, Yushi Uno

Theoretical Computer Science 729 巻頁： 1 - 10 2018年6月

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：Elsevier B.V.

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

DOI： 10.1016/j.tcs.2018.03.016

Scopus

researchmap

Reconfiguration of colorable sets in classes of perfect graphs 査読有り

Takehiro Ito, Yota Otachi

Leibniz International Proceedings in Informatics, LIPIcs 101 巻頁： 271 - 2713 2018年6月

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

A set of vertices in a graph is c-colorable if the subgraph induced by the set has a proper c-coloring. In this paper, we study the problem of finding a step-by-step transformation (reconfiguration) between two c-colorable sets in the same graph. This problem generalizes the well-studied Independent Set Reconfiguration problem. As the first step toward a systematic understanding of the complexity of this general problem, we study the problem on classes of perfect graphs. We first focus on interval graphs and give a combinatorial characterization of the distance between two c-colorable sets. This gives a linear-time algorithm for finding an actual shortest reconfiguration sequence for interval graphs. Since interval graphs are exactly the graphs that are simultaneously chordal and co-comparability, we then complement the positive result by showing that even deciding reachability is PSPACE-complete for chordal graphs and for co-comparability graphs. The hardness for chordal graphs holds even for split graphs. We also consider the case where c is a fixed constant and show that in such a case the reachability problem is polynomial-time solvable for split graphs but still PSPACE-complete for co-comparability graphs. The complexity of this case for chordal graphs remains unsettled. As by-products, our positive results give the first polynomial-time solvable cases (split graphs and interval graphs) for Feedback Vertex Set Reconfiguration.

DOI： 10.4230/LIPIcs.SWAT.2018.27

Scopus

researchmap

Parameterized orientable deletion 査読有り国際共著

Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Yota Otachi, Florian Sikora

Leibniz International Proceedings in Informatics, LIPIcs 101 巻頁： 241 - 2413 2018年6月

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

A graph is d-orientable if its edges can be oriented so that the maximum in-degree of the resulting digraph is at most d. d-orientability is a well-studied concept with close connections to fundamental graph-theoretic notions and applications as a load balancing problem. In this paper we consider the d-Orientable Deletion problem: given a graph G = (V, E), delete the minimum number of vertices to make G d-orientable. We contribute a number of results that improve the state of the art on this problem. Specifically: We show that the problem is W[2]-hard and log n-inapproximable with respect to k, the number of deleted vertices. This closes the gap in the problem’s approximability. We completely characterize the parameterized complexity of the problem on chordal graphs: it is FPT parameterized by d + k, but W-hard for each of the parameters d, k separately. We show that, under the SETH, for all d, , the problem does not admit a (d + 2 − )tw, algorithm where tw is the graph’s treewidth, resolving as a special case an open problem on the complexity of PseudoForest Deletion. We show that the problem is W-hard parameterized by the input graph’s clique-width. Complementing this, we provide an algorithm running in time dO(d·cw), showing that the problem is FPT by d + cw, and improving the previously best know algorithm for this case.

DOI： 10.4230/LIPIcs.SWAT.2018.24

Scopus

researchmap

How Bad is the Freedom to Flood-It? 査読有り国際共著

Rémy Belmonte, Mehdi Khosravian Ghadikolaei, Masashi Kiyomi, Michael Lampis, Yota Otachi

Leibniz International Proceedings in Informatics, LIPIcs 100 巻頁： 51 - 513 2018年6月

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

FIXED-FLOOD-IT and FREE-FLOOD-IT are combinatorial problems on graphs that generalize a very popular puzzle called Flood-It. Both problems consist of recoloring moves whose goal is to produce a monochromatic ("flooded") graph as quickly as possible. Their difference is that in FREE-FLOOD-IT the player has the additional freedom of choosing the vertex to play in each move. In this paper, we investigate how this freedom affects the complexity of the problem. It turns out that the freedom is bad in some sense. We show that some cases trivially solvable for FIXED-FLOOD-IT become intractable for FREE-FLOOD-IT. We also show that some tractable cases for FIXED-FLOOD-IT are still tractable for FREE-FLOOD-IT but need considerably more involved arguments. We finally present some combinatorial properties connecting or separating the two problems. In particular, we show that the length of an optimal solution for FIXED-FLOOD-IT is always at most twice that of FREE-FLOOD-IT, and this is tight.

DOI： 10.4230/LIPIcs.FUN.2018.5

Scopus

researchmap

A faster parameterized algorithm for PSEUDOFOREST DELETION 査読有り国際共著

Hans L. Bodlaender, Hirotaka Ono, Yota Otachi

Discrete Applied Mathematics 236 巻頁： 42 - 56 2018年2月

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：Elsevier B.V.

A pseudoforest is a graph where each connected component contains at most one cycle, or alternatively, a graph that can be turned into a forest by removing at most one edge from each connected component. In this paper, we show that the following problem can be solved in O(3knkO(1)) time: given a graph G and an integer k, can we delete at most k vertices from G such that we obtain a pseudoforest? The result improves upon an earlier result by Philip et al. (2015) who gave a (nonlinear) 7.56knO(1)-time algorithm both in the exponential factor depending on k as well as in the polynomial factor depending on n.

DOI： 10.1016/j.dam.2017.10.018

Scopus

researchmap

Space-effcient algorithms for longest increasing subsequence 査読有り国際共著

Masashi Kiyomi, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui

Leibniz International Proceedings in Informatics, LIPIcs 96 巻頁： 44:1-44:15 2018年2月

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

Given a sequence of integers, we want to find a longest increasing subsequence of the sequence. It is known that this problem can be solved in O(n log n) time and space. Our goal in this paper is to reduce the space consumption while keeping the time complexity small. For n = s = n, we present algorithms that use O(s log n) bits and O(1 s · n2 · log n) time for computing the length of a longest increasing subsequence, and O(1 s · n2 · log2 n) time for finding an actual subsequence. We also show that the time complexity of our algorithms is optimal up to polylogarithmic factors in the framework of sequential access algorithms with the prescribed amount of space.

DOI： 10.4230/LIPIcs.STACS.2018.44

Scopus

researchmap

Induced Minor Free Graphs: Isomorphism and Clique-Width 査読有り国際共著

Rémy Belmonte, Yota Otachi, Pascal Schweitzer

Algorithmica 80 巻 ( 1 ) 頁： 29 - 47 2018年1月

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：Springer New York LLC

Given two graphs G and H, we say that G contains H as an induced minor if a graph isomorphic to H can be obtained from G by a sequence of vertex deletions and edge contractions. We study the complexity of Graph Isomorphism on graphs that exclude a fixed graph as an induced minor. More precisely, we determine for every graph H that Graph Isomorphism is polynomial-time solvable on H-induced-minor-free graphs or that it is GI-complete. Additionally, we classify those graphs H for which H-induced-minor-free graphs have bounded clique-width. These two results complement similar dichotomies for graphs that exclude a fixed graph as an induced subgraph, minor, or subgraph.

DOI： 10.1007/s00453-016-0234-8

Scopus

researchmap

　前のページ - 次のページ　

<大舘 陽太>

論文 - 大舘 陽太

<大舘　陽太>

論文 - 大舘　陽太