研究者詳細 - 小野　廣隆

論文 - 小野　廣隆

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

Shortest Longest-Path Graph Orientations

Asahiro Y., Jansson J., Melkman A.A., Miyano E., Ono H., Xue Q., Zakov S.

Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics 14422 LNCS 巻頁： 141 - 154 2024年

掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics

We consider a graph orientation problem that can be viewed as a generalization of Minimum Graph Coloring. Our problem takes as input an undirected graph G= (V, E) in which every edge { u, v} ∈ E has two (potentially different and not necessarily positive) weights representing the lengths of its two possible directions (u, v) and (v, u), and asks for an orientation, i.e., an assignment of a direction to each edge of G, such that the length of a longest simple directed path in the resulting directed graph is minimized. A longest path in a graph is not always a maximal path when some edges have negative lengths, so the problem has two variants depending on whether all simple directed paths or maximal simple directed paths only are taken into account in the definition. We prove that the problems are NP-hard to approximate even if restricted to subcubic planar graphs, and develop fast polynomial-time algorithms for both problem variants for three classes of graphs: path graphs, cycle graphs, and star graphs.

DOI： 10.1007/978-3-031-49190-0_10

Scopus

Enumerating Minimal Vertex Covers and Dominating Sets with Capacity and/or Connectivity Constraints

Kobayashi, Y; Kurita, K; Matsui, Y; Ono, H

COMBINATORIAL ALGORITHMS, IWOCA 2024 14764 巻頁： 232 - 246 2024年

An improved spectral lower bound of treewidth.

Tatsuya Gima, Tesshu Hanaka, Kohei Noro, Hirotaka Ono 0001, Yota Otachi

CoRR abs/2404.08520 巻 2024年

On the complexity of finding a spanning even tree in a graph.

Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, Yasuko Matsui, Atsuki Nagao, Hirotaka Ono 0001, Kazuhisa Seto

CoRR abs/2412.17307 巻 2024年

Reconfiguration of cliques in a graph Open Access

Ito, T; Ono, H; Otachi, Y

DISCRETE APPLIED MATHEMATICS 333 巻頁： 43 - 58 2023年7月

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

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 from the viewpoint of polynomial-time solvability. 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. Furthermore, we show that 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.1016/j.dam.2023.01.026

Web of Science

Scopus

Grouped Domination Parameterized by Vertex Cover, Twin Cover, and Beyond

Hanaka T., Ono H., Otachi Y., Uda S.

Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics 13898 巻頁： 263 - 277 2023年4月

掲載種別：論文集(書籍)内論文出版者・発行元：Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics

A dominating set S of graph G is called an r-grouped domR such that the size of each unit is r and the subgraph of G induced by is connected. The concept of r-grouped dominating sets generalizes several well-studied variants of dominating sets with requirements for connected component sizes, such as the ordinary dominating sets , paired dominating sets), and connected dominating sets (r is arbitrary and . In this paper, we investigate the computational complexity of r -Grouped Dominating Set, which is the problem of deciding whether a given graph has an r-grouped dominating set with at most k units. For general r, r -Grouped Dominating Set is hard to solve in various senses because the hardness of the connected dominating set is inherited. We thus focus on the case in which r is a constant or a parameter, but we see that r -Grouped Dominating Set for every fixed is still hard to solve. From the observations about the hardness, we consider the parameterized complexity concerning well-studied graph structural parameters. We first see that r -Grouped Dominating Set is fixed-parameter tractable for r and treewidth, which is derived from the fact that the condition of r-grouped domination for a constant r can be represented as monadic second-order logic This fixed-parameter tractability is good news, but the running time is not practical. We then design an -time algorithm for general where is the twin cover number, which is a parameter between vertex cover number and clique-width. For paired dominating set and trio dominating set, i.e., we can speed up the algorithm, whose running time becomes We further argue the relationship between FPT results and graph parameters, which draws the parameterized complexity landscape of r -Grouped Dominating Set.

DOI： 10.1007/978-3-031-30448-4_19

Scopus

Enumerating minimal vertex covers and dominating sets with capacity and/or connectivity constraints.

Yasuaki Kobayashi, Kazuhiro Kurita, Yasuko Matsui, Hirotaka Ono

CoRR abs/2308.16426 巻 2023年

Approximation Algorithms for the Longest Run Subsequence Problem Open Access

Asahiro, Y; Eto, H; Gong, MY; Jansson, J; Lin, GH; Miyano, E; Ono, H; Tanaka, S

34TH ANNUAL SYMPOSIUM ON COMBINATORIAL PATTERN MATCHING, CPM 2023 259 巻頁： 2 - 12 2023年

掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：Leibniz International Proceedings in Informatics Lipics

We study the approximability of the Longest Run Subsequence problem (LRS for short). For a string S = s1 · · · sn over an alphabet Σ, a run of a symbol σ ∈ Σ in S is a maximal substring of consecutive occurrences of σ. A run subsequence S′ of S is a sequence in which every symbol σ ∈ Σ occurs in at most one run. Given a string S, the goal of LRS is to find a longest run subsequence S∗ of S such that the length |S∗| is maximized over all the run subsequences of S. It is known that LRS is APX-hard even if each symbol has at most two occurrences in the input string, and that LRS admits a polynomial-time k-approximation algorithm if the number of occurrences of every symbol in the input string is bounded by k. In this paper, we design a polynomial-time k+1/2-approximation algorithm for LRS under the k-occurrence constraint on input strings. For the case k = 2, we further improve the approximation ratio from 2/3 to 4/3.

DOI： 10.4230/LIPIcs.CPM.2023.2

Open Access

Web of Science

Scopus

その他リンク： https://dblp.uni-trier.de/db/conf/cpm/cpm2023.html#AsahiroEG0LMOT23

On the Computational Complexity of Generalized Common Shape Puzzles.

Mutsunori Banbara, Shin-ichi Minato, Hirotaka Ono, Ryuhei Uehara

CoRR abs/2305.10749 巻 2023年

Theoretical Aspects of Generating Instances with Unique Solutions: Pre-assignment Models for Unique Vertex Cover.

Takashi Horiyama, Yasuaki Kobayashi, Hirotaka Ono 0001, Kazuhisa Seto, Ryu Suzuki

CoRR abs/2312.10599 巻 2023年

Shortest Beer Path Queries based on Graph Decomposition.

Tesshu Hanaka, Hirotaka Ono 0001, Kunihiko Sadakane, Kosuke Sugiyama

CoRR abs/2307.02787 巻 2023年

Turning Tiles is PSPACE-complete.

Kanae Yoshiwatari, Hironori Kiya, Koki Suetsugu, Tesshu Hanaka, Hirotaka Ono 0001

CoRR abs/2310.01983 巻 2023年

Parameterized Complexity of (A, l)-Path Packing 査読有り Open Access

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

ALGORITHMICA 84 巻 ( 4 ) 頁： 871 - 895 2022年4月

記述言語：英語掲載種別：研究論文（研究会，シンポジウム資料等）出版者・発行元：Algorithmica

Given a graph G= (V, E) , A⊆ V, and integers k and ℓ, the (A, ℓ) -Path Packing problem asks to find k vertex-disjoint paths of length exactly ℓ 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+ ℓ. Additionally, we study a variant called Short A-Path Packing that asks to find k vertex-disjoint paths of length at mostℓ. We show that all our positive results on the exact-length version can be translated to this version and show the hardness of the cases where |A| or ℓ is a constant.

DOI： 10.1007/s00453-021-00875-y

Open Access

Web of Science

Scopus

Upper and lower degree-constrained graph orientation with minimum penalty 査読有り Open Access

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

THEORETICAL COMPUTER SCIENCE 900 巻頁： 53 - 78 2022年1月

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

In the degree-constrained graph orientation problem, the input is an unweighted, undirected graph G=(V,E) and nonnegative integers a<inf>v</inf> and b<inf>v</inf> (with a<inf>v</inf>≤b<inf>v</inf>) for each v∈V, and the objective is to assign a direction to every edge in E in such a way that for each v∈V, the number of outgoing edges in the resulting directed graph lies in the interval [a<inf>v</inf>,b<inf>v</inf>]. When such an orientation does not exist, it is desirable to find an orientation that best fits the condition instead. In this paper, we consider the problem of finding an orientation that minimizes the total penalty ∑<inf>v∈V</inf>c<inf>v</inf>, where c<inf>v</inf> is a penalty incurred whenever a vertex v violates its degree constraints. As penalty functions, convex, concave, and step functions are considered in this paper. We show that the problem with any convex penalty function can be solved in O(|E|1.5min⁡{log⁡(|E|⋅C),|E|0.5log⁡Δlog⁡|E|}) time, where Δ and C are the maximum degree and the largest magnitude of a penalty, respectively. In contrast, we show APX-hardness of the problem with step or concave functions. For trees and graphs with treewidth τ, the problem with any penalty function can be solved exactly in O(|V|log⁡Δ) time and O(τ2Δ2τ+2|V|) time, respectively. Finally, we consider the generalization of the problem to edge-weighted graphs and establish strong bounds on its inapproximability that hold even in the special case of stars. On the positive side, we can extend our algorithms for unweighted version of the problem to obtain pseudo-polynomial-time algorithms for the edge-weighted problem variant when restricted to trees and graphs with bounded treewidth. Also, we design a PTAS and a linear-time algorithm for stars with further restrictions on the degree constraints and edge weights.

DOI： 10.1016/j.tcs.2021.11.019

Web of Science

Scopus

構造的オラクルによる不完全情報TANHINMINのモデリング査読有り Open Access

KIYA Hironori, OHTO Katsuki, ONO Hirotaka

情報処理学会論文誌トランザクション数理モデル化と応用(Web) 15 巻 ( 1 ) 頁： 10 - 17 2022年1月

Winner Determination Algorithms for Graph Games with Matching Structures

Yoshiwatari K., Kiya H., Hanaka T., Ono H.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 13270 LNCS 巻頁： 509 - 522 2022年

記述言語：日本語掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Cram, Domineering, and Arc Kayles are well-studied combinatorial games. They are interpreted as edge-selecting-type games on graphs, and the selected edges during a game form a matching. In this paper, we define a generalized game called Colored Arc Kayles, which includes these games. Colored Arc Kayles is played on a graph whose edges are colored in black, white, or gray, and black (resp., white) edges can be selected only by the black (resp., white) player, although gray edges can be selected by both black and white players. We first observe that the winner determination for Colored Arc Kayles can be done in O∗(2n) time by a simple algorithm, where n is the order of a graph. We then focus on the vertex cover number, which is linearly related to the number of turns, and show that Colored Arc Kayles, BW-Arc Kayles, and Arc Kayles are solved in time O∗(1.4143τ2+3.17τ), O∗(1.3161τ2+4τ), and O∗(1.1893τ2+6.34τ), respectively, where τ is the vertex cover number. Furthermore, we present an O∗((n/ ν+ 1 )ν) -time algorithm for Arc Kayles, where ν is neighborhood diversity. We finally show that Arc Kayles on trees can be solved in O∗(2n2) (= O(1. 4143n) ) time, which improves O∗(3n3) (= O(1. 4423n) ) by a direct adjustment of the analysis of Bodlaender et al.’s O∗(3n3) -time algorithm for Node Kayles.

DOI： 10.1007/978-3-031-06678-8_37

Scopus

その他リンク： https://dblp.uni-trier.de/db/conf/iwoca/iwoca2022.html#YoshiwatariKHO22

Capacitated Network Design Games on a Generalized Fair Allocation Model.

Tesshu Hanaka, Toshiyuki Hirose, Hirotaka Ono

21st International Conference on Autonomous Agents and Multiagent Systems(AAMAS) 頁： 1616 - 1617 2022年