研究者詳細 - 大舘　陽太

論文 - 大舘　陽太

分割表示 151 件中 121 - 140 件目／全件表示 >>

Polynomial-Time Algorithm for Sliding Tokens on Trees 査読有り国際共著

Erik D. Demaine, Martin L. Demaine, Eli Fox-Epstein, Duc A. Hoang, Takehiro Ito, Hirotaka Ono, Yota Otachi, Ryuhei Uehara, Takeshi Yamada

ALGORITHMS AND COMPUTATION, ISAAC 2014 8889 巻頁： 389 - 400 2014年

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

Suppose that we are given two independent sets I-b and I-r of a graph such that vertical bar I-b vertical bar = vertical bar I-r vertical bar, and imagine that a token is placed on each vertex in I-b. Then, the sliding token problem is to determine whether there exists a sequence of independent sets which transforms I-b and I-r so that each independent set in the sequence results from the previous one by sliding exactly one token along an edge in the graph. This problem is known to be PSPACE-complete even for planar graphs, and also for bounded treewidth graphs. In this paper, we show that the problem is solvable for trees in quadratic time. Our proof is constructive: for a yes-instance, we can find an actual sequence of independent sets between I-b and I-r whose length (i. e., the number of token-slides) is quadratic. We note that there exists an infinite family of instances on paths for which any sequence requires quadratic length.

DOI： 10.1007/978-3-319-13075-0_31

Base location problems for base-monotone regions 査読有り

Jinhee Chun, Takashi Horiyama, Takehiro Ito, Natsuda Kaothanthong, Hirotaka Ono, Yota Otachi, Takeshi Tokuyama, Ryuhei Uehara, Takeaki Uno

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7748 巻頁： 53 - 64 2013年

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

The problem of decomposing a pixel grid into base-monotone regions was first studied in the context of image segmentation. It is known that for a given pixel grid and baselines, one can compute in polynomial time a maximum-weight region that can be decomposed into disjoint base-monotone regions [Chun et al. ISAAC 2009]. We continue this line of research and show the NP-hardness of the problem of optimally locating k baselines in a given n ×n pixel grid. We also present an O(n3)-time 2-approximation algorithm for this problem. We then study two related problems, the k base-segment problem and the quad-decomposition problem, and present some complexity results for them. © 2013 Springer-Verlag.

DOI： 10.1007/978-3-642-36065-7_7

On complexity of flooding games on graphs with interval representations 査読有り

Hiroyuki Fukui, Yota Otachi, Ryuhei Uehara, Takeaki Uno, Yushi Uno

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 8296 巻頁： 73 - 84 2013年

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

The flooding games, which are called Flood-It, Mad Virus, or HoneyBee, are a kind of coloring games and they have been becoming popular online. In these games, each player colors one specified cell in his/her turn, and all connected neighbor cells of the same color are also colored by the color. This flooding or coloring spreads on the same color cells. It is natural to consider the coloring games on general graphs: Once a vertex is colored, the flooding flows along edges in the graph. Recently, computational complexities of the variants of the flooding games on several graph classes have been studied. We investigate the one player flooding games on some graph classes characterized by interval representations. Our results state that the number of colors is a key parameter to determine the computational complexity of the flooding games. © 2013 Springer-Verlag.

DOI： 10.1007/978-3-642-45281-9_7

Isomorphism on Subgraph-Closed Graph Classes: A Complexity Dichotomy and Intermediate Graph Classes 査読有り国際共著

Yota Otachi, Pascal Schweitzer

ALGORITHMS AND COMPUTATION 8283 巻頁： 111 - 118 2013年

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

We study the graph isomorphism problem for graph classes defined by sets of forbidden subgraphs. We show that there is a complexity dichotomy in case the set of forbidden subgraphs is finite. More precisely, we show that the problem is polynomial-time solvable if the forbidden set contains a forest of subdivided stars and is graph isomorphism complete otherwise. We also show that, assuming that the graph isomorphism problem is not polynomial-time solvable in general, there is no such dichotomy for the cases of infinite sets of forbidden subgraphs. To this end, we conditionally show that there exists a graph class closed under taking subgraphs with intermediate isomorphism problem, i.e., a class on which the isomorphism problem is neither polynomial-time solvable nor graph isomorphism complete.

DOI： 10.1007/978-3-642-45030-3_11

THE PATH-DISTANCE-WIDTH OF HYPERCUBES 査読有り

Yota Otachi

DISCUSSIONES MATHEMATICAE GRAPH THEORY 33 巻 ( 2 ) 頁： 467 - 470 2013年

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

The path-distance-width of a connected graph G is the minimum integer w satisfying that there is a nonempty subset of S subset of V(G) such that the number of the vertices with distance i from S is at most w for any nonnegative integer i.
In this note, we determine the path-distance-width of hypercubes.

DOI： 10.7151/dmgt.1682

Bounded representations of interval and proper interval graphs 査読有り国際共著

Martin Balko, Pavel Klavík, Yota Otachi

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 8283 巻頁： 535 - 546 2013年

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

Klavík et al. [arXiv:1207.6960] recently introduced a generalization of recognition called the bounded representation problem which we study for the classes of interval and proper interval graphs. The input gives a graph G and in addition for each vertex v two intervals ℒv and ℛv called bounds. We ask whether there exists a bounded representation in which each interval Iv has its left endpoint in ℒv and its right endpoint in . We show that the problem can be solved in linear time for interval graphs and in quadratic time for proper interval graphs. Robert's Theorem states that the classes of proper interval graphs and unit interval graphs are equal. Surprisingly, the bounded representation problem is polynomially solvable for proper interval graphs and NP-complete for unit interval graphs [Klavík et al., arxiv:1207.6960]. So unless P = NP, the proper and unit interval representations behave very differently. The bounded representation problem belongs to a wider class of restricted representation problems. These problems are generalizations of the well-understood recognition problem, and they ask whether there exists a representation of G satisfying some additional constraints. The bounded representation problems generalize many of these problems. © 2013 Springer-Verlag.

DOI： 10.1007/978-3-642-45030-3_50

Subgraph isomorphism in graph classes 査読有り

Shuji Kijima, Yota Otachi, Toshiki Saitoh, Takeaki Uno

DISCRETE MATHEMATICS 312 巻 ( 21 ) 頁： 3164 - 3173 2012年11月

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

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

DOI： 10.1016/j.disc.2012.07.010

Parameterized Complexity of the Spanning Tree Congestion Problem 査読有り国際共著

Hans L. Bodlaender, Fedor V. Fomin, Petr A. Golovach, Yota Otachi, Erik Jan van Leeuwen

ALGORITHMICA 64 巻 ( 1 ) 頁： 85 - 111 2012年9月

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

We study the problem of determining the spanning tree congestion of a graph. We present some sharp contrasts in the parameterized complexity of this problem. First, we show that on apex-minor-free graphs, a general class of graphs containing planar graphs, graphs of bounded treewidth, and graphs of bounded genus, the problem to determine whether a given graph has spanning tree congestion at most k can be solved in linear time for every fixed k. We also show that for every fixed k and d the problem is solvable in linear time for graphs of degree at most d. In contrast, if we allow only one vertex of unbounded degree, the problem immediately becomes NP-complete for any fixed ka parts per thousand yen8. Moreover, the hardness result holds for graphs excluding the complete graph on 6 vertices as a minor. We also observe that for ka parts per thousand currency sign3 the problem becomes polynomially time solvable.

DOI： 10.1007/s00453-011-9565-7

Efficient enumeration of ordered trees with k leaves 査読有り

Katsuhisa Yamanaka, Yota Otachi, Shin-ichi Nakano

THEORETICAL COMPUTER SCIENCE 442 巻頁： 22 - 27 2012年7月

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

This paper presents a simple algorithm to generate all ordered trees with exactly n vertices including exactly k leaves. The best known algorithm generates such trees in O(n - k) time per tree, whereas our algorithm generates such trees in O(1) time per tree in the worst case. (C) 2011 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.tcs.2011.01.017

Enumerating All Rooted Trees Including k Leaves 査読有り

Masanobu Ishikawa, Katsuhisa Yamanaka, Yota Otachi, Shin-ichi Nakano

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS E95D 巻 ( 3 ) 頁： 763 - 768 2012年3月

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG

This paper presents an efficient algorithm to generate all (unordered) rooted trees with exactly vertices including exactly k leaves. There are known results on efficient enumerations of some classes of graphs embedded on a plane, for instance, biconnected and triconnected triangulations [3], [6], and floorplans [4]. On the other hand, it is difficult to enumerate a class of graphs without a fixed embedding. The paper is on enumeration of rooted trees without a fixed embedding. We already proposed an algorithm to generate all "ordered" trees with 17 vertices including k leaves [11], while the algorithm cannot seem to efficiently generate all (unordered) rooted trees with it vertices including k leaves. We design a simple tree structure among such trees, then by traversing the tree structure we generate all such trees in constant time per tree in the worst case. By repeatedly applying the algorithm for each k = 1, 2, . . . , n - 1, we can also generate all rooted trees with exactly n vertices.

DOI： 10.1587/transinf.E95.D.763

その他リンク： http://dblp.uni-trier.de/db/journals/ieicet/ieicet95d.html#journals/ieicet/IshikawaYON12

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

Toshiki Saitoh, Yota Otachi, Katsuhisa Yamanaka, Ryuhei Uehara

Journal of Discrete Algorithms 10 巻 ( 1 ) 頁： 84 - 97 2012年1月

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

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

A 4.31-Approximation for the Geometric Unique Coverage Problem on Unit Disks 査読有り

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

ALGORITHMS AND COMPUTATION, ISAAC 2012 7676 巻頁： 372 - 381 2012年

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

We give an improved approximation algorithm for the unique unit-disk coverage problem: Given a set of points and a set of unit disks, both in the plane, we wish to find a subset of disks that maximizes the number of points contained in exactly one disk in the subset. Erlebach and van Leeuwen (2008) introduced this problem as the geometric version of the unique coverage problem, and gave a polynomial-time 18-approximation algorithm. In this paper, we improve this approximation ratio 18 to 2 + 4/root 3 + epsilon (< 4.3095 + epsilon) for any fixed constant epsilon > 0. Our algorithm runs in polynomial time which depends exponentially on 1/epsilon. The algorithm can be generalized to the budgeted unique unit-disk coverage problem in which each point has a profit, each disk 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.

DOI： 10.1007/978-3-642-35261-4_40

On bipartite powers of bigraphs 査読有り

Yoshio Okamoto, Yota Otachi, Ryuhei Uehara

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE 14 巻 ( 2 ) 頁： 11-20 2012年

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

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7357 巻頁： 24 - 35 2012年

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

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 (2008) introduced this problem as the geometric version of the unique coverage problem, and the best approximation ratio by van Leeuwen (2009) 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. © 2012 Springer-Verlag.

DOI： 10.1007/978-3-642-31155-0_3

Isomorphism for Graphs of Bounded Connected-Path-Distance-Width 査読有り

Yota Otachi

ALGORITHMS AND COMPUTATION, ISAAC 2012 7676 巻頁： 455 - 464 2012年

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

We show that Graph Isomorphism problem (GI) can be solved in O(n(2)) time for graphs of bounded connected-path-distance-width, and more generally, in O(n(c+1)) time for graphs of bounded c-connected-path-distance-width, where n is the number of vertices. These results extend the result of Yamazaki, Bodlaender, de Fluiter, and Thilikos [Isomorphism for graphs of bounded distance width. Algorithmica 24, 105-127 (1999)], who showed the fixed-parameter tractability of GI parameterized by rooted-path-distance-width.

DOI： 10.1007/978-3-642-35261-4_48

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

Pavel Klavik, Jan Kratochvil, Yota Otachi, Toshiki Saitoh

ALGORITHMS AND COMPUTATION, ISAAC 2012 7676 巻頁： 444 - 454 2012年

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

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 pre-drawn subtrees, the number of components and the size of the tree T'. We describe an interesting relation with integer partition problems. The problem 3-Partition is used in the NP-completeness reductions. The BIN-PACKING problem is closely related to the extension of interval graphs when space in T' is limited, and we obtain "equivalency" with BIN PACKING.

DOI： 10.1007/978-3-642-35261-4_47

Spanning tree congestion of k-outerplanar graphs 査読有り国際共著

Hans L. Bodlaender, Kyohei Kozawa, Takayoshi Matsushima, Yota Otachi

DISCRETE MATHEMATICS 311 巻 ( 12 ) 頁： 1040 - 1045 2011年6月

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

In 1987, Simonson conjectured that every k-outerplanar graph of maximum degree d has spanning tree congestion at most k . d [S. Simonson, A variation on the min cut linear arrangement problem, Math. Syst. Theory 20(1987)235-252]. We show that his conjecture is true and the bound is tight for outerplanar graphs and k-outerplanar graphs of maximum degree 4. We give a precise characterization of the spanning tree congestion of outerplanar graphs, and thus show that the spanning tree congestion of outerplanar graphs can be determined in linear time. (C) 2011 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.disc.2011.03.002

Bandwidth and pathwidth of three-dimensional grids 査読有り

Yota Otachi, Ryohei Suda

DISCRETE MATHEMATICS 311 巻 ( 10-11 ) 頁： 881 - 887 2011年6月

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

We study the bandwidth and the pathwidth of multi-dimensional grids. It can be shown for grids, that these two parameters are equal to a more basic graph parameter, the vertex boundary width. Using this fact, we determine the bandwidth and the pathwidth of three-dimensional grids, which were known only for the cubic case. As a by-product, we also determine the two parameters of multi-dimensional grids with relatively large maximum factors. (C) 2011 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.disc.2011.02.019

Hardness results and an exact exponential algorithm for the spanning tree congestion problem 査読有り

Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno

Journal of Graph Algorithms and Applications 15 巻 ( 6 ) 頁： 727 - 751 2011年

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

Spanning tree congestion is a relatively new graph parameter, which has been studied intensively. This paper studies the complexity of the problem to determine the spanning tree congestion for non-sparse graph classes, while it was investigated for some sparse graph classes before. We prove that the problem is NP-hard even for chain graphs and split graphs. To cope with the hardness of the problem, we present a fast (exponential- time) exact algorithm that runs in O*(2 n) time, where n denotes the number of vertices. Additionally, we present simple combinatorial lem- mas, which yield a constant-factor approximation algorithm for cographs, and a linear-time algorithm for chordal cographs.

DOI： 10.7155/jgaa.00246

Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem 査読有り

Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno

THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2011 6648 巻頁： 452 - 462 2011年

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

Spanning tree congestion is a relatively new graph parameter, which has been studied intensively. This paper studies the complexity of the problem to determine the spanning tree congestion for non-sparse graph classes, while it was investigated for some sparse graph classes before. We prove that the problem is NP-hard even for chain graphs and split graphs. To cope with the hardness of the problem, we present a fast (exponential-time) exact algorithm that runs in O*(2(n)) time, where n denotes the number of vertices. Additionally, we provide a constant-factor approximation algorithm for cographs, and a linear-time algorithm for chordal cographs.

DOI： 10.1007/978-3-642-20877-5_44

　前のページ - 次のページ　

1
2
3
4
5
6
7
8