研究者詳細 - 小野　廣隆

論文 - 小野　廣隆

分割表示 236 件中 41 - 60 件目／全件表示 >>

Maximizing Utilitarian and Egalitarian Welfare of Fractional Hedonic Games on Tree-Like Graphs

Hanaka T., Ikeyama A., Ono H.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 14461 LNCS 巻頁： 392 - 405 2023年12月

担当区分：責任著者出版者・発行元：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Fractional hedonic games are coalition formation games where the utility of a player is determined by the average value they assign to the members of their coalition. These games are a variation of graph hedonic games, which are a class of coalition formation games that can be succinctly represented. Due to their applicability in network clustering and their relationship to graph hedonic games, fractional hedonic games have been extensively studied from various perspectives. However, finding welfare-maximizing partitions in fractional hedonic games is a challenging task due to the nonlinearity of utilities. In fact, it has been proven to be NP-hard in general and can be solved in polynomial time only for a limited number of graph classes, such as trees. This paper presents (pseudo)polynomial-time algorithms to compute welfare-maximizing partitions in fractional hedonic games on tree-like graphs. We consider two types of social welfare measures: utilitarian and egalitarian. Tree-like graphs refer to graphs with bounded treewidth and block graphs. An NP-hardness result demonstrates that the pseudopolynomial-time solvability is the best possible under the assumption P ≠ NP.

DOI： 10.1007/978-3-031-49611-0_28

Scopus

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

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年

On the Computational Complexity of Generalized Common Shape Puzzles.

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

CoRR abs/2305.10749 巻 2023年

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

Asahiro Y., Gong M., Lin G., Ono H., Eto H., Jansson J., Miyano E., Tanaka S.

Leibniz International Proceedings in Informatics, LIPIcs 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

Scopus

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

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 (<i>A</i>, <i>l</i>)-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 av and bv (with av≤bv) 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 [av,bv]. 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 ∑v∈Vcv, where cv 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のモデリング査読有り

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年

Winner Determination Algorithms for Graph Games with Matching Structures.

Tesshu Hanaka, Hironori Kiya, Hirotaka Ono, Kanae Yoshiwatari

CoRR abs/2211.05307 巻 2022年

組合せゲームに対するアルゴリズム論的アプローチ

木谷裕紀, 小野廣隆

システム／制御／情報 65 巻 ( 10 ) 頁： 415 - 420 2021年10月

Computing the Winner of 2-Player TANHINMIN

Kiya Hironori, Ohto Katsuki, Ono Hirotaka

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES E104.A 巻 ( 9 ) 頁： 1134 - 1141 2021年9月

担当区分：最終著者記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：一般社団法人電子情報通信学会

DAIHINMIN, which means Grand Pauper, is a popular playing-card game in Japan. TANHINMIN is a simplified variant of DAIHINMIN, which was proposed by Nishino in 2007 in order to investigate the mathematical properties of DAIHINMIN. In this paper, we consider a 2-player generalized TANHINMIN, where the deck size is arbitrary n. We present a linear-time algorithm that determines which player has a winning strategy after all cards are distributed to the players.

DOI： 10.1587/transfun.2020dmp0026

Web of Science

Scopus

Graph Orientation with Edge Modifications 査読有り国際共著 Open Access

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

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 32 巻 ( 02 ) 頁： 209 - 233 2021年2月

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

The goal of an outdegree-constrained edge-modification problem is to find a spanning subgraph or supergraph H of an input undirected graph G such that either: (Type I) the number of edges in H is minimized or maximized and H can be oriented to satisfy some specified constraints on the vertices' resulting outdegrees; or: (Type II) among all subgraphs or supergraphs of G that can be constructed by deleting or inserting a fixed number of edges, H admits an orientation optimizing some objective involving the vertices' outdegrees. This paper introduces eight new outdegree-constrained edge-modification problems related to load balancing called (Type I) MIN-DEL-MAX, MIN-INS-MIN, MAX-INS-MAX, and MAX-DEL-MIN and (Type II) p-DEL-MAX, p-INS-MIN, p-INS-MAX, and p-DEL-MIN. In each of the eight problems, the input is a graph and the goal is to delete or insert edges so that the resulting graph has an orientation in which the maximum outdegree (taken over all vertices) is small or the minimum outdegree is large. We first present a framework that provides algorithms for solving all eight problems in polynomial time on unweighted graphs. Next we investigate the inapproximability of the edge-weighted versions of the problems, and design polynomial-time algorithms for six of the problems on edge-weighted trees.

DOI： 10.1142/S012905412150012X

Web of Science

Scopus

Computing L(p, 1)-Labeling with Combined Parameters 査読有り

Hanaka T., Kawai K., Ono H.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 12635 LNCS 巻頁： 208 - 220 2021年2月

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

Given a graph, an L(p, 1)-labeling of the graph is an assignment f from the vertex set to the set of nonnegative integers such that for any pair of vertices (u, v), | f(u) - f(v) | ≥ p if u and v are adjacent, and f(u) ≠ f(v) if u and v are at distance 2. The L(p, 1)-labeling problem is to minimize the span of f (i.e., maxu∈V(f(u) ) - minu∈V(f(u) ) + 1 ). It is known to be NP-hard even for graphs of maximum degree 3 or graphs with tree-width 2, whereas it is fixed-parameter tractable with respect to vertex cover number. Since the vertex cover number is a kind of the strongest parameter, there is a large gap between tractability and intractability from the viewpoint of parameterization. To fill up the gap, in this paper, we propose new fixed-parameter algorithms for L(p, 1)-Labeling by the twin cover number plus the maximum clique size and by the tree-width plus the maximum degree. These algorithms reduce the gap in terms of several combinations of parameters.

DOI： 10.1007/978-3-030-68211-8_17

Scopus

Fairness norm through social networks: a simulation approach Open Access

Rifki O., Ono H.

Computational Social Networks 8 巻 ( 1 ) 2021年

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

Recently there has been an increased interest in adopting game-theoretic models to social norms. Most of these approaches are generally lacking a structure linking the local level of the ‘norm’ interaction to its global ‘social’ nature. Although numerous studies examined local-interaction games, where the emphasis is placed on neighborhood relations, regarding social network as a whole unique entity seems to be quite limited. In this paper, we conduct a series of simulation experiments to examine the effects that a network topology could have on the speed of emergence of the social norm. The emphasis is placed on the fairness norm in the ultimatum game context, by considering three network type models (Barabási–Albert, Watts–Strogatz and Erdős–Rényi) and several intrinsic topological properties.

DOI： 10.1186/s40649-021-00100-4

Open Access

Scopus

　前のページ - 次のページ　

<小野 廣隆>

論文 - 小野 廣隆

<小野　廣隆>

論文 - 小野　廣隆