研究者詳細 - 大舘　陽太

論文 - 大舘　陽太

分割表示 151 件中 81 - 100 件目／全件表示 >>

Vertex deletion problems on chordal graphs 査読有り国際共著

Yixin Cao, Yuping Ke, Yota Otachi, Jie You

Leibniz International Proceedings in Informatics, LIPIcs 93 巻頁： 22:1-22:14 - 86 2018年1月

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

Containing many classic optimization problems, the family of vertex deletion problems has an important position in algorithm and complexity study. The celebrated result of Lewis and Yannakakis gives a complete dichotomy of their complexity. It however has nothing to say about the case when the input graph is also special. This paper initiates a systematic study of vertex deletion problems from one subclass of chordal graphs to another. We give polynomial-time algorithms or proofs of NP-completeness for most of the problems. In particular, we show that the vertex deletion problem from chordal graphs to interval graphs is NP-complete.

DOI： 10.4230/LIPIcs.FSTTCS.2017.22

Computational Complexity of Robot Arm Simulation Problems. 査読有り

Tianfeng Feng, Takashi Horiyama, Yoshio Okamoto, Yota Otachi, Toshiki Saitoh, Takeaki Uno, Ryuhei Uehara

Combinatorial Algorithms - 29th International Workshop, IWOCA 2018, Singapore, July 16-19, 2018, Proceedings 10979 巻頁： 177 - 188 2018年

Exact Algorithms for the Max-Min Dispersion Problem. 査読有り

Toshihiro Akagi, Tetsuya Araki, Takashi Horiyama, Shin-Ichi Nakano, Yoshio Okamoto, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, Takeaki Uno, Kunihiro Wasa

Frontiers in Algorithmics - 12th International Workshop, FAW 2018, Guangzhou, China, May 8-10, 2018, Proceedings 10823 巻頁： 263 - 272 2018年

Vertex deletion problems on chordal graphs. 査読有り国際共著

Yixin Cao, Yuping Ke, Yota Otachi, Jie You

Theoretical Computer Science 745 巻頁： 75 - 86 2018年

Safe sets in graphs: Graph classes and structural parameters 査読有り国際共著

Raquel Águeda, Nathann Cohen, Shinya Fujita, Sylvain Legay, Yannis Manoussakis, Yasuko Matsui, Leandro Montero, Reza Naserasr, Hirotaka Ono, Yota Otachi, Tadashi Sakuma, Zsolt Tuza, Renyu Xu

Journal of Combinatorial Optimization 36 巻 ( 4 ) 頁： 1 - 22 2017年11月

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

A safe set of a graph (Formula presented.) is a non-empty subset S of V such that for every component A of G[S] and every component B of (Formula presented.), we have (Formula presented.) whenever there exists an edge of G between A and B. In this paper, we show that a minimum safe set can be found in polynomial time for trees. We then further extend the result and present polynomial-time algorithms for graphs of bounded treewidth, and also for interval graphs. We also study the parameterized complexity. We show that the problem is fixed-parameter tractable when parameterized by the solution size. Furthermore, we show that this parameter lies between the tree-depth and the vertex cover number. We then conclude the paper by showing hardness for split graphs and planar graphs.

DOI： 10.1007/s10878-017-0205-2

Hitori numbers 査読有り

Akira Suzuki, Masashi Kiyomi, Yota Otachi, Kei Uchizawa, Takeaki Uno

Journal of Information Processing 25 巻頁： 695 - 707 2017年8月

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：Information Processing Society of Japan

Hitori is a popular “pencil-and-paper” puzzle defined as follows. In n-hitori, we are given an n×n rectangular grid in which each square is labeled with a positive integer, and the goal is to paint a subset of the squares so that the following three rules are satisfied: Rule 1) No row or column has a repeated unpainted label
Rule 2) Painted squares are never (horizontally or vertically) adjacent
Rule 3) The unpainted squares are all connected (via horizontal and vertical connections). The grid is called an instance of n-hitori if it has a unique solution. In this paper, we introduce hitori number and maximum hitori number which are defined as follows: For every integer n, hitori number h(n) is the minimum number of different integers used in an instance where the minimum is taken over all the instances of n-hitori. For every integer n, maximum hitori number h(n) is the maximum number of different integers used in an instance where the maximum is taken over all the instances of n-hitori. We then prove that ⌊(2n - 1)/3⌋ ≤ h(n) ≤ 2⌊n/3⌋ + 1 for n ≥ 2 and ⌊(4n2 - 4n + 11)/5⌋ ≥ h(n) ≤ (4n2 + 2n - 2)/5 for n ≤ 3.

DOI： 10.2197/ipsjjip.25.695

Extending Partial Representations of Interval Graphs 査読有り国際共著

Pavel Klavik, Jan Kratochvil, Yota Otachi, Toshiki Saitoh, Tomas Vyskoil

ALGORITHMICA 78 巻 ( 3 ) 頁： 945 - 967 2017年7月

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

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

Alliances in graphs of bounded clique-width 査読有り

Masashi Kiyomi, Yota Otachi

DISCRETE APPLIED MATHEMATICS 223 巻頁： 91 - 97 2017年5月

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：ELSEVIER SCIENCE BV

An alliance in a graph is a set of vertices that is either safe under attacks from the neighborhood (defensive), capable of attacking its neighbors (offensive), or simultaneously defensive and offensive (powerful). An alliance is global if all nonmembers are adjacent to some members of the alliance. The concept of alliances was introduced by Kristiansen et al. (2004). After that many results concerning the complexity for finding a minimum alliance were shown. It was shown that the problem of finding a minimum alliance of any variant is NP-hard in general. For some variants, it was shown that the problem becomes polynomial time solvable when restricted to trees or series-parallel graphs.
In this paper, we show that the problems for all variants are efficiently solvable for much larger graph classes. We present a polynomial-time algorithm for graphs of bounded clique-width. We also show that the problem is fixed-parameter tractable when parameterized by the vertex cover number. (C) 2017 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2017.02.004

Extending Partial Representations of Proper and Unit Interval Graphs 査読有り国際共著

Pavel Klavik, Jan Kratochvil, Yota Otachi, Ignaz Rutter, Toshiki Saitoh, Maria Saumell, Tomas Vyskocil

ALGORITHMICA 77 巻 ( 4 ) 頁： 1071 - 1104 2017年4月

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

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 , 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

A faster parameterized algorithm for pseudoforest deletion 査読有り国際共著

Hans L. Bodlaender, Hirotaka Ono, Yota Otachi

Leibniz International Proceedings in Informatics, LIPIcs 63 巻頁： 7:1-7:12 2017年2月

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

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. [MFCS 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.4230/LIPIcs.IPEC.2016.7

Thin strip graphs 査読有り

Takashi Hayashi, Akitoshi Kawamura, Yota Otachi, Hidehiro Shinohara, Koichi Yamazaki

DISCRETE APPLIED MATHEMATICS 216 巻頁： 203 - 210 2017年1月

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：ELSEVIER SCIENCE BV

A unit disk graph is a c-strip graph if it has a unit disk representation in which all centers of the unit disks lie between two parallel lines at distance c. The classes of c-strip graphs for various c are studied in the literature. For example, the 0-strip graphs are exactly the unit interval graphs, and every root 3/2-strip graph is a co-comparability graph. In this paper, we introduce the class of thin strip graphs and study their properties. A graph is a thin strip graph if it is a c-strip graph for every c > 0. We show that there is no constant t such that the t-strip graphs are exactly the thin strip graphs. We also show that the class of thin strip graphs properly includes the class of mixed unit interval graphs. (C) 2015 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2015.01.018

Ferrers dimension of grid intersection graphs 査読有り国際共著

Steven Chaplick, Pavol Hell, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara

DISCRETE APPLIED MATHEMATICS 216 巻頁： 130 - 135 2017年1月

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：ELSEVIER SCIENCE BV

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. (C) 2015 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2015.05.035

Efficient enumeration of maximal k-degenerate subgraphs in a chordal graph 査読有り国際共著

Alessio Conte, Mamadou Moustapha Kanté, Yota Otachi, Takeaki Uno, Kunihiro Wasa

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 10392 巻頁： 150 - 161 2017年

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：Springer Verlag

In this paper, we consider the problem of listing the maximal k-degenerate induced subgraphs of a chordal graph, and propose an output-sensitive algorithm using delay O(m\\cdot \\omega (G)) for any n-vertex chordal graph with m edges, where \\omega (G) \\le n is the maximum size of a clique in G. The problem generalizes that of enumerating maximal independent sets and maximal induced forests, which correspond to respectively 0-degenerate and 1-degenerate subgraphs.

DOI： 10.1007/978-3-319-62389-4_13

Degree-constrained orientation of maximum satisfaction: Graph classes and parameterized complexity 査読有り国際共著

Hans L. Bodlaender, Hirotaka Ono, Yota Otachi

Leibniz International Proceedings in Informatics, LIPIcs 64 巻頁： 20.1 - 20.12 2016年12月

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

The problem MAX W-LIGHT (MAX W-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, MAX W-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 MAX W-LIGHT, we need an additional condition of a polynomial upper bound on the number of potential maximal cliques to apply the metatheorem by Fomin, Todinca, and Villanger [SIAM J. Comput., 44(1):57-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.4230/LIPIcs.ISAAC.2016.20

On the classes of interval graphs of limited nesting and count of lengths 査読有り国際共著

Pavel Klavík, Yota Otachi, Jiří Šejnoha

Leibniz International Proceedings in Informatics, LIPIcs 64 巻頁： 45.1 - 45.13 2016年12月

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

In 1969, Roberts introduced proper and unit interval graphs and proved that these classes are equal. Natural generalizations of unit interval graphs called k-length interval graphs were considered in which the number of different lengths of intervals is limited by k. Even after decades of research, no insight into their structure is known and the complexity of recognition is open even for k = 2. We propose generalizations of proper interval graphs called k-nested interval graphs in which there are no chains of k + 1 intervals nested in each other. It is easy to see that k-nested interval graphs are a superclass of k-length interval graphs. We give a linear-time recognition algorithm for k-nested interval graphs. This algorithm adds a missing piece to Gajarský et al. [FOCS 2015] to show that testing FO properties on interval graphs is FPT with respect to the nesting k and the length of the formula, while the problem is W[2]-hard when parameterized just by the length of the formula. Further, we show that a generalization of recognition called partial representation extension is polynomial-time solvable for k-nested interval graphs, while it is NP-hard for k-length interval graphs, even when k = 2.

DOI： 10.4230/LIPIcs.ISAAC.2016.45

Finding a chain graph in a bipartite permutation graph 査読有り

Masashi Kiyomi, Yota Otachi

INFORMATION PROCESSING LETTERS 116 巻 ( 9 ) 頁： 569 - 573 2016年9月

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：ELSEVIER SCIENCE BV

We present a polynomial-time algorithm for solving SUBGRAPH ISOMORPHISM where the base graphs are bipartite permutation graphs and the pattern graphs are chain graphs. (C) 2016 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.ip1.2016.04.006

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

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

Leibniz International Proceedings in Informatics, LIPIcs 51 巻頁： 46.1 - 46.10 2016年6月

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

It is proved that the total length of any set of countably many rectifiable curves, whose union meets all straight lines that intersect the unit square U, is at least 2.00002. This is the first improvement on the lower bound of 2 by Jones in 1964. A similar bound is proved for all convex sets U other than a triangle.

DOI： 10.4230/LIPIcs.SoCG.2016.46

Polynomial-time algorithms for SUBGRAPH ISOMORPHISM in small graph classes of perfect graphs 査読有り

Matsuo Konagaya, Yota Otachi, Ryuhei Uehara

DISCRETE APPLIED MATHEMATICS 199 巻頁： 37 - 45 2016年1月

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：ELSEVIER SCIENCE BV

Given two graphs, SUBGRAPH ISOMORPHISM is the problem of deciding whether the first graph (the base graph) contains a subgraph isomorphic to the second one (the pattern graph). This problem is NP-complete even for very restricted graph classes such as connected proper interval graphs. Only a few cases are known to be polynomial-time solvable even if we restrict the graphs to be perfect. For example, if both graphs are co-chain graphs, then the problem can be solved in linear time.
In this paper, we present a polynomial-time algorithm for the case where the base graphs are chordal graphs and the pattern graphs are co-chain graphs. We also present a linear-time algorithm for the case where the base graphs are trivially perfect graphs and the pattern graphs are threshold graphs. These results answer some of the open questions of Kijima et al. (2012). To present a complexity contrast, we then show that even if the base graphs are somewhat restricted perfect graphs, the problem of finding a pattern graph that is a chain graph, a co-chain graph, or a threshold graph is NP-complete. (C) 2015 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2015.01.040

On the treewidth of toroidal grids 査読有り

Masashi Kiyomi, Yoshio Okamoto, Yota Otachi

DISCRETE APPLIED MATHEMATICS 198 巻頁： 303 - 306 2016年1月

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：ELSEVIER SCIENCE BV

Many graph parameters of grid-like graphs are studied because of their algorithmic consequences. An important concept in this context is that of treewidth. Treewidth of graphs is a graph parameter for measuring how close a graph is to a tree. In this paper, we study the treewidth of toroidal grids and show that the treewidth of the n x n toroidal grid is either 2n - 2 or 2n - 1. We then show that these bounds are tight in some cases. To show the lower bounds, we construct brambles of high orders. (C) 2015 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2015.06.027

A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares 査読有り

Takehiro Ito, Shin-ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno, Yushi Uno

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 51 巻頁： 25 - 39 2016年1月

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：ELSEVIER SCIENCE BV

We give a polynomial-time approximation scheme for the unique unit-square coverage problem: given a set of points and a set of axis-parallel unit squares, both in the plane, we wish to find a subset of squares that maximizes the number of points contained in exactly one square in the subset. Erlebach and van Leeuwen [9] introduced this problem as the geometric version of the unique coverage problem, and the best approximation ratio by van Leeuwen [21] before our work was 2. Our scheme can be generalized to the budgeted unique unit-square coverage problem, in which each point has a profit, each square has a cost, and we wish to maximize the total profit of the uniquely covered points under the condition that the total cost is at most a given bound. (C) 2015 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.comgeo.2015.10.004

　前のページ - 次のページ　

1
2
3
4
5
6
7
8