研究者詳細 - 小野　廣隆

論文 - 小野　廣隆

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

Reallocation Problems with Minimum Completion Time.

Toshimasa Ishii, Jun Kawahara, Kazuhisa Makino, Hirotaka Ono

CoRR abs/2111.02579 巻 2021年

Graph orientation with splits 査読有り国際共著 Open Access

Asahiro, Y; Jansson, J; Miyano, E; Nikpey, H; Ono, H

THEORETICAL COMPUTER SCIENCE 844 巻頁： 16 - 25 2020年12月

記述言語：日本語掲載種別：研究論文（学術雑誌）出版者・発行元：Theoretical Computer Science

The Minimum Maximum Outdegree Problem (MMO) is to assign a direction to every edge in an input undirected, edge-weighted graph so that the maximum weighted outdegree taken over all vertices becomes as small as possible. In this paper, we introduce a new variant of MMO called the p-Split Minimum Maximum Outdegree Problem (p-Split-MMO) in which one is allowed to perform a sequence of p split operations on the vertices before orienting the edges, for some specified non-negative integer p, and study its computational complexity.

DOI： 10.1016/j.tcs.2020.07.013

Web of Science

Scopus

Exact algorithms for the repetition-bounded longest common subsequence problem 査読有り国際共著 Open Access

Asahiro, Y; Jansson, J; Lin, GH; Miyano, E; Ono, H; Utashima, T

THEORETICAL COMPUTER SCIENCE 838 巻頁： 238 - 249 2020年10月

記述言語：日本語掲載種別：研究論文（学術雑誌）出版者・発行元：Theoretical Computer Science

In this paper, we study exact, exponential-time algorithms for a variant of the classic LONGEST COMMON SUBSEQUENCE problem called the REPETITION-BOUNDED LONGEST COMMON SUBSEQUENCE problem (or RBLCS, for short): Let an alphabet S be a finite set of symbols and an occurrence constraint Cocc be a function Cocc:S→N, assigning an upper bound on the number of occurrences of each symbol in S. Given two sequences X and Y over the alphabet S and an occurrence constraint Cocc, the goal of RBLCS is to find a longest common subsequence of X and Y such that each symbol s∈S appears at most Cocc(s) times in the obtained subsequence. The special case where Cocc(s)=1 for every symbol s∈S is known as the REPETITION-FREE LONGEST COMMON SUBSEQUENCE problem (RFLCS) and has been studied previously; e.g., in [1], Adi et al. presented a simple (exponential-time) exact algorithm for RFLCS. However, they did not analyze its time complexity in detail, and to the best of our knowledge, there are no previous results on the running times of any exact algorithms for this problem. Without loss of generality, we will assume that |X|≤|Y| and |X|=n. In this paper, we first propose a simpler algorithm for RFLCS based on the strategy used in [1] and show explicitly that its running time is O(1.44225n). Next, we provide a dynamic programming (DP) based algorithm for RBLCS and prove that its running time is O(1.44225n) for any occurrence constraint Cocc, and even less in certain special cases. In particular, for RFLCS, our DP-based algorithm runs in O(1.41422n) time, which is faster than the previous one. Furthermore, we prove NP-hardness and APX-hardness results for RBLCS on restricted instances.

DOI： 10.1016/j.tcs.2020.07.042

Open Access

Web of Science

Scopus

Parameterized complexity of independent set reconfiguration problems 査読有り国際共著

Ito Takehiro, Kaminski Marcin, Ono Hirotaka, Suzuki Akira, Uehara Ryuhei, Yamanaka Katsuhisa

DISCRETE APPLIED MATHEMATICS 283 巻頁： 336 - 345 2020年9月

記述言語：日本語掲載種別：研究論文（学術雑誌）出版者・発行元：Discrete Applied Mathematics

Suppose that we are given two independent sets I0 and Ir of a graph such that |I0|=|Ir|, and imagine that a token is placed on each vertex in I0. Then, the TOKEN JUMPING problem is to determine whether there exists a sequence of independent sets which transforms I0 into Ir so that each independent set in the sequence results from the previous one by moving exactly one token to another vertex. Therefore, all independent sets in the sequence must be of the same cardinality. This problem is PSPACE-complete even for planar graphs with maximum degree three. In this paper, we first show that the problem is W[1]-hard when parameterized only by the number of tokens. We then give an FPT algorithm for general graphs when parameterized by both the number of tokens and the maximum degree. Our FPT algorithm can be modified so that it finds an actual sequence of independent sets between I0 and Ir with the minimum number of token movements. We finally show that one of the results for TOKEN JUMPING can be extended to a more generalized reconfiguration problem for independent sets, called TOKEN ADDITION AND REMOVAL.

DOI： 10.1016/j.dam.2020.01.022

Web of Science

Scopus

Independent Set Reconfiguration Parameterized by Modular-Width 査読有り

Belmonte, R; Hanaka, T; Lampis, M; Ono, H; Otachi, Y

ALGORITHMICA 82 巻 ( 9 ) 頁： 2586 - 2605 2020年9月

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

Independent Set Reconfiguration is one of the most well-studied problems in the setting of combinatorial reconfiguration. It is known that the problem is PSPACE-complete even for graphs of bounded bandwidth. This fact rules out the tractability of parameterizations by most well-studied structural parameters as most of them generalize bandwidth. In this paper, we study the parameterization by modular-width, which is not comparable with bandwidth. We show that the problem parameterized by modular-width is fixed-parameter tractable under all previously studied rules TAR, TJ, and TS. The result under TAR resolves an open problem posed by Bonsma (J Graph Theory 83(2):164–195, 2016).

DOI： 10.1007/s00453-020-00700-y

Web of Science

Scopus

その他リンク： http://link.springer.com/article/10.1007/s00453-020-00700-y/fulltext.html

Parameterized Complexity of (A,l)-Path Packing 査読有り国際共著

Belmonte R., Hanaka T., Kanzaki M., Kiyomi M., Kobayashi Y., Kobayashi Y., Lampis M., Ono H., Otachi Y.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 12126 LNCS 巻頁： 43 - 55 2020年6月

記述言語：日本語掲載種別：論文集(書籍)内論文出版者・発行元：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Given a graph G = (V, E), (Formula Presented), and integers k and ℓ, the (A, ℓ)-Path Packing problem asks to find k vertex-disjoint paths of length ℓ that have endpoints in A and internal points in V \ A. We study the parameterized complexity of this problem with parameters |A|, ℓ, k, treewidth, pathwidth, and their combinations. We present sharp complexity contrasts with respect to these parameters. Among other results, we show that the problem is polynomial-time solvable when ℓ ≤ 3, while it is NP-complete for constant ℓ ≥ 4. We also show that the problem is W[1]-hard parameterized by pathwidth+|A|, while it is fixed-parameter tractable parameterized by treewidth + ℓ.

DOI： 10.1007/978-3-030-48966-3_4

Scopus

Parameterized complexity of safe set 査読有り国際共著

Belmonte R., Hanaka T., Katsikarelis I., Lampis M., Ono H., Otachi Y.

Journal of Graph Algorithms and Applications 24 巻 ( 3 ) 頁： 215 - 245 2020年4月

記述言語：日本語掲載種別：研究論文（学術雑誌）出版者・発行元：Journal of Graph Algorithms and Applications

In this paper we study the problem of finding a small safe set S in a graph G, i.e., a non-empty set of vertices such that no connected component of G[S] is adjacent to a larger component in G − S. We enhance our understanding of the problem from the viewpoint of parameterized complexity by showing that (1) the problem is W[2]-hard when parameterized by the pathwidth pw and cannot be solved in time no(pw) unless the ETH is false, (2) it admits no polynomial kernel parameterized by the vertex cover number vc unless PH = Σp but (3) it is fixed-parameter tractable (FPT) when parameterized by3,the neighborhood diversity nd, and (4) it can be solved in time nf(cw) for some double exponential function f where cw is the clique-width. We also present (5) a faster fixed-parameter algorithm when parameterized by the solution size.

DOI： 10.7155/jgaa.00528

Scopus

Space-Efficient Algorithms for Longest Increasing Subsequence 査読有り国際共著

Kiyomi, M; Ono, H; Otachi, Y; Schweitzer, P; Tarui, J

THEORY OF COMPUTING SYSTEMS 64 巻 ( 3 ) 頁： 522 - 541 2020年4月

記述言語：日本語掲載種別：研究論文（学術雑誌）出版者・発行元：Theory of Computing Systems

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(nlog 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(slog n) bits and O(1s⋅n2⋅logn) time for computing the length of a longest increasing subsequence, and O(1s⋅n2⋅log2n) 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.1007/s00224-018-09908-6

Web of Science

Scopus

その他リンク： http://link.springer.com/article/10.1007/s00224-018-09908-6/fulltext.html

Hedonic Seat Arrangement Problems. 査読有り国際誌

Hans L. Bodlaender, Tesshu Hanaka, Lars Jaffke, Hirotaka Ono, Yota Otachi, Tom C. van der Zanden

AAMAS '20: Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems 頁： 1777 - 1779 2020年

The computational complexity of the gear placement problem Open Access

Hama, VMF; Kanazawa, S; Hu, Y; Imahori, S; Ono, H; Yagiura, M

JOURNAL OF ADVANCED MECHANICAL DESIGN SYSTEMS AND MANUFACTURING 14 巻 ( 5 ) 頁： JAMDSM0069 - JAMDSM0069 2020年

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：一般社団法人日本機械学会

In this paper, we analyze the complexity of the gear placement problem (GPP). In the GPP, we are given a rectangular plane, called a gearbox, on which a torque generator source and a set of gears, called target gears, are placed. The task is to find a placement of a set of gears called sub-gears, to connect every target gear to the torque generator source so that every target gear rotates in a given direction. The objective is to minimize the number of sub-gears to be used. We prove that the GPP is NP-hard by giving a reduction from the Hamiltonian path problem on 3-regular planar graphs, which is known to be NP-complete, to the GPP. We also present an upper bound for the number of sub-gears to be placed.

DOI： 10.1299/jamdsm.2020jamdsm0069

Two-Player Competitive Diffusion Game: Graph Classes and the Existence of a Nash Equilibrium 査読有り

Fukuzono Naoka, Hanaka Tesshu, Kiya Hironori, Ono Hirotaka, Yamaguchi Ryogo

SOFSEM 2020: THEORY AND PRACTICE OF COMPUTER SCIENCE 12011 巻頁： 627 - 635 2020年

The competitive diffusion game is a game-theoretic model of information spreading on a graph proposed by Alon et al. (2010). In the model, a player chooses an initial vertex of the graph, from which information by the player spreads through the edges connected with the initial vertex. If a vertex that is not yet influenced by any information receives information by a player, it is influenced by the information and it diffuses it to adjacent vertices. A vertex that simultaneously receives two or more types of information does not diffuse any type of information from then on. The objective of a player is to maximize the number of vertices influenced by the player’s information. In this paper, we investigate the existence of a pure Nash equilibrium of the two-player competitive diffusion game on chordal and its related graphs. We show that a pure Nash equilibrium always exists on block graphs, split graphs and interval graphs, all of which are well-known subclasses of chordal graphs. On the other hand, we show that there is an instance with no pure Nash equilibrium on (strongly) chordal graphs; the boundary of the existence of a pure Nash equilibrium is found.

DOI： 10.1007/978-3-030-38919-2_52

Web of Science

Scopus

Fair Ride Allocation on a Line.

Yuki Amano, Ayumi Igarashi, Yasushi Kawase, Kazuhisa Makino, Hirotaka Ono

CoRR abs/2007.08045 巻 2020年