研究者詳細 - 大舘　陽太

論文 - 大舘　陽太

分割表示 151 件中 101 - 120 件目／全件表示 >>

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, Yota Otachi, Tadashi Sakuma, Zsolt Tuza, Renyu Xu

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 10043 巻頁： 241 - 253 2016年

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

A safe set of a graph G = (V,E) is a non-empty subset S of V such that for every component A of G[S] and every component B of G[V \\ S], we have |A| ≥ |B| 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 of the problem. We show that the problem is fixed-parameter tractable when parameterized by the solution size. Furthermore, we show that this parameter lies between tree-depth and vertex cover number.

DOI： 10.1007/978-3-319-48749-6_18

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

Remy Belmonte, Yota Otachi, Pascal Schweitzer

GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE 9224 巻頁： 299 - 311 2016年

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

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 isomorphism complete. Additionally, we classify those graphs H for which H-induced-minor-free graphs have bounded clique-width. Those two results complement similar dichotomies for graphs that exclude a fixed graph as an induced subgraph, minor or subgraph.

DOI： 10.1007/978-3-662-53174-7_21

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

THEORETICAL COMPUTER SCIENCE 600 巻頁： 132 - 142 2015年10月

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

Suppose that we are given two independent sets I-b and I-r of a graph such that vertical bar l(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 into 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 thus study the problem restricted to trees, and give the following three results: (1) the decision problem is solvable in linear time; (2) for a yes-instance, we can find in quadratic time an actual sequence of independent sets between I-b and I-r whose length (i.e., the number of token-slides) is quadratic; and (3) there exists an infinite family of instances on paths for which any sequence requires quadratic length. (C) 2015 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.tcs.2015.07.037

Extending partial representations of subclasses of chordal graphs 査読有り国際共著

Pavel Klavik, Jan Kratochvil, Yota Otachi, Toshiki Saitoh

THEORETICAL COMPUTER SCIENCE 576 巻頁： 85 - 101 2015年4月

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

Chordal graphs are intersection graphs of subtrees of a tree T. We investigate the complexity of the partial representation extension problem for chordal graphs. A partial representation specifies a tree T' and some pre-drawn subtrees of T'. It asks whether it is possible to construct a representation inside a modified tree T which extends the partial representation (i.e., keeps the pre-drawn subtrees unchanged).
We consider four modifications of T' leading to vastly different problems: (i) T = T', (ii) T is a subdivision of T', (iii) T is a supergraph of T', and (iv) T' is a topological minor of T. In some cases, it is interesting to consider the complexity even when 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. We further study the parametrized complexity of the problems when parametrized by the number of pre-drawn subtrees, the number of components of the input graph G and the size of the tree T'.
We describe an interesting relation with integer partition problems. The problem 3-PARTITION is used for all NP-completeness reductions. When the space in T' is limited, partial representation extension of proper interval graphs is "equivalent" to the BINPACKING problem. (C) 2015 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.tcs.2015.02.007

Secure Sets and Defensive Alliances in Graphs: A Faster Algorithm and Improved Bounds 査読有り国際共著

Kazuyuki Amano, Kyaw May Oo, Yota Otachi, Ryuhei Uehara

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS E98D 巻 ( 3 ) 頁： 486 - 489 2015年3月

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

Secure sets and defensive alliances in graphs are studied. They are sets of vertices that are safe in some senses. In this paper, we first present a fixed-parameter algorithm for finding a small secure set, whose running time ismuch faster than the previously known one. We then present improved bound on the smallest sizes of defensive alliances and secure sets for hypercubes. These results settle some open problems paused recently.

DOI： 10.1587/transinf.2014FCP0007

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

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

Katsuhisa Yamanaka, Takashi Horiyama, David Kirkpatrick, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, Yushi Uno

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 9214 巻頁： 619 - 628 2015年

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

We investigate the computational complexity of the following problem. We are given a graph in which each vertex has the current and target colors. 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 every constant 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.

DOI： 10.1007/978-3-319-21840-3_51

COMPLETELY INDEPENDENT SPANNING TREES IN (PARTIAL) k-TREES 査読有り

Masayoshi Matsushita, Yota Otachi, Toru Araki

DISCUSSIONES MATHEMATICAE GRAPH THEORY 35 巻 ( 3 ) 頁： 427 - 437 2015年

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

Two spanning trees T-1 and T-2 of a graph G are completely independent if, for any two vertices u and v, the paths from u to v in T-1 and T-2 are internally disjoint. For a graph G, we denote the maximum number of pairwise completely independent spanning trees by cist(G). In this paper, we consider cist(G) when G is a partial k-tree.
First we show that [k/2] <= cist(G) <= k - 1 for any k-tree G. Then we show that for any p is an element of {[k/2],..., k - 1}, there exist infinitely many k-trees G such that cist(G) = p. Finally we consider algorithmic aspects for computing cist(G). Using Courcelle's theorem, we show that there is a linear-time algorithm that computes cist(G) for a partial k-tree, where k is a fixed constant.

DOI： 10.7151/dmgt.1806

Competitive diffusion on weighted graphs 査読有り

Takehiro Ito, Yota Otachi, Toshiki Saitoh, Hisayuki Satoh, Akira Suzuki, Kei Uchizawa, Ryuhei Uehara, Katsuhisa Yamanaka, Xiao Zhou

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 9214 巻頁： 422 - 433 2015年

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

Consider an undirected and vertex-weighted graph modeling a social network, where the vertices represent individuals, the edges do connections among them, and weights do levels of importance of individuals. In the competitive diffusion game, each of a number of players chooses a vertex as a seed to propagate his/her idea which spreads along the edges in the graph. The objective of every player is to maximize the sum of weights of vertices infected by his/her idea. In this paper, we study a computational problem of asking whether a pure Nash equilibrium exists in a given graph, and present several negative and positive results with regard to graph classes. We first prove that the problem is W[1]-hard when parameterized by the number of players even for unweighted graphs. We also show that the problem is NP-hard even for series-parallel graphs with positive integer weights, and is NP-hard even for forests with arbitrary integer weights. Furthermore, we show that the problem for forests of paths with arbitrary weights is solvable in pseudo-polynomial time
and it is solvable in quadratic time if a given graph is unweighted. We also prove that the problem is solvable in polynomial time for chain graphs, cochain graphs, and threshold graphs with arbitrary integer weights.

DOI： 10.1007/978-3-319-21840-3_35

Reconfiguration of Cliques in a Graph 査読有り

Takehiro Ito, Hirotaka Ono, Yota Otachi

THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2015) 9076 巻頁： 212 - 223 2015年

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

We study reconfiguration problems for cliques in a graph, which determine whether there exists a sequence of cliques that transforms a given clique into another one in a step-by-step fashion. As one step of a transformation, we consider three different types of rules, which are defined and studied in reconfiguration problems for independent sets. We first prove that all the three rules are equivalent in cliques. We then show that the problems are PSPACE-complete for perfect graphs, while we give polynomial-time algorithms for several classes of graphs, such as even-hole-free graphs and cographs. In particular, the shortest variant, which computes the shortest length of a desired sequence, can be solved in polynomial time for chordal graphs, bipartite graphs, planar graphs, and bounded treewidth graphs.

DOI： 10.1007/978-3-319-17142-5_19

Sliding Token on Bipartite Permutation Graphs 査読有り国際共著

Eli Fox-Epstein, Duc A. Hoang, Yota Otachi, Ryuhei Uehara

ALGORITHMS AND COMPUTATION, ISAAC 2015 9472 巻頁： 237 - 247 2015年

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

Sliding Token is a natural reconfiguration problem in which vertices of independent sets are iteratively replaced by neighbors. We develop techniques that may be useful in answering the conjecture that Sliding Token is polynomial-time decidable on bipartite graphs. Along the way, we give efficient algorithms for Sliding Token on bipartite permutation and bipartite distance-hereditary graphs.

DOI： 10.1007/978-3-662-48971-0_21

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

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

THEORETICAL COMPUTER SCIENCE 555 巻頁： 71 - 84 2014年10月

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

A base-monotone region with a base is a subset of the cells in a pixel grid such that if a cell is contained in the region then so are the ones on a shortest path from the cell to the base. The problem of decomposing a pixel grid into disjoint base-monotone regions was first studied in the context of image segmentation. It is known that for a given pixel grid and base-lines, one can compute in polynomial time a maximum-weight region that can be decomposed into disjoint base-monotone regions with respect to the given baselines (Chun et al., 2012 [4]). We continue this line of research and show the NP-hardness of the problem of optimally locating k base-lines in a given n x n pixel grid. We then present an O (n(3))-time 2-approximation algorithm for this problem. We also study two related problems, the k base-segment problem and the quad-decomposition problem, and present some complexity results for them. (C) 2013 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.tcs.2013.11.030

Efficient algorithms for network localization using cores of underlying graphs 査読有り

Meng Li, Yota Otachi, Takeshi Tokuyama

THEORETICAL COMPUTER SCIENCE 553 巻頁： 18 - 26 2014年10月

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

Network localization is important for networks with no prefixed positions of network nodes such as sensor networks. We are given a subset of the set of ((n)(2)) pairwise distances among n sensors in some Euclidean space. We want to determine the positions of each sensor from the (partial) distance information. The input can be seen as an edge weighted graph. In this paper, we present some efficient algorithms that solve this problem using the structures of input graphs, which we call their cores. For instance, we present a polynomial-time algorithm solving the network localization problem for graphs with connected dominating sets of bounded size. This algorithm allows us to have fixed-parameter tractable algorithms for some restricted instances such as graphs with connected vertex covers of bounded size. (C) 2014 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.tcs.2014.02.020

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

THEORETICAL COMPUTER SCIENCE 544 巻頁： 14 - 31 2014年8月

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

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

DOI： 10.1016/j.tcs.2014.04.014

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

Yota Otachi, Toshiki Saitoh, Katsuhisa Yamanaka, Shuji Kijima, Yoshio Okamoto, Hirotaka Ono, Yushi Uno, Koichi Yamazaki

DISCRETE APPLIED MATHEMATICS 168 巻頁： 69 - 77 2014年5月

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

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

DOI： 10.1016/j.dam.2012.11.015

Lower bounds for treewidth of product graphs 査読有り

Kyohei Kozawa, Yota Otachi, Koichi Yamazaki

DISCRETE APPLIED MATHEMATICS 162 巻頁： 251 - 258 2014年1月

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

Two lower bounds for the treewidth of product graphs are presented in terms of the bramble number. The first bound is that the bramble number of the Cartesian product of graphs G(1) and G(2) must be at least the product of the Hadwiger number of G(1) and the PI number of G(2), where the PI number is a new graph parameter introduced in this paper. The second bound is that the bramble number of the strong product of graphs G(1) and G(2) must be at least the product of the Hadwiger number of G(1) and the bramble number of G(2). We also demonstrate applications of the lower bounds. (C) 2013 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dam.2013.08.005

Intersection Dimension of Bipartite Graphs 査読有り国際共著

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

THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2014) 8402 巻頁： 323 - 340 2014年

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

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.

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

Polynomial-Time Algorithms for SUBGRAPH ISOMORPHISM in Small Graph Classes of Perfect Graphs 査読有り

Matsuo Konagaya, Yota Otachi, Ryuhei Uehara

THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2014) 8402 巻頁： 216 - 228 2014年

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

Given two graphs, Subgraph Isomorphism is the problem of deciding whether the first graph (the base graph) contains a subgraph isomorphic to the second graph (the pattern graph). This problem is NP-complete 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. [Discrete Math. 312, pp. 3164-3173, 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.

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

Reduction Techniques for Graph Isomorphism in the Context of Width Parameters 査読有り国際共著

Yota Otachi, Pascal Schweitzer

ALGORITHM THEORY - SWAT 2014 8503 巻頁： 368 - + 2014年

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

We study the parameterized complexity of the graph isomorphism problem when parameterized by width parameters related to tree decompositions. We apply the following technique to obtain fixed-parameter tractability for such parameters. We first compute an isomorphism invariant set of potential bags for a decomposition and then apply a restricted version of the Weisfeiler-Lehman algorithm to solve isomorphism. With this we show fixed-parameter tractability for several parameters and provide a unified explanation for various isomorphism results concerned with parameters related to tree decompositions.
As a possibly first step towards intractability results for parameterized graph isomorphism we develop an fpt Turing-reduction from strong tree width to the a priori unrelated parameter maximum degree.

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

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

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

ALGORITHM THEORY - SWAT 2014 8503 巻頁： 253 - + 2014年

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

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.

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

Depth-First Search Using O(n) Bits 査読有り国際共著

Tetsuo Asano, Taisuke Izumi, Masashi Kiyomi, Matsuo Konagaya, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui, Ryuhei Uehara

ALGORITHMS AND COMPUTATION, ISAAC 2014 8889 巻頁： 553 - 564 2014年

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

We provide algorithms performing Depth-First Search (DFS) on a directed or undirected graph with n vertices and m edges using only O(n) bits. One algorithm uses O(n) bits and runs in O(mlog n) time. Another algorithm uses n+ o(n) bits and runs in polynomial time. Furthermore, we show that DFS on a directed acyclic graph can be done in space n/2(Omega(root log n)) and in polynomial time, and we also give a simple linear-time O(log n)-space algorithm for the depth-first traversal of an undirected tree. Finally, we also show that for a graph having an O(1)-size feedback set, DFS can be done in O(log n) space. Our algorithms are based on the analysis of properties of DFS and applications of the s-t connectivity algorithms due to Reingold and Barnes et al., both of which run in sublinear space.

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

　前のページ - 次のページ　

1
2
3
4
5
6
7
8