4 citations · 13 across the 17 of their papers we have counts for
23 papers
Enumerating minimal vertex covers and dominating sets with capacity and/or connectivity constraints
Yasuaki Kobayashi, Kazuhiro Kurita, Kevin Mann +2
In this paper, we consider the problems of enumerating minimal vertex covers and minimal dominating sets with capacity and/or connectivity constraints. We develop polynomial-delay…
Shortest Beer Path Queries based on Graph Decomposition
Tesshu Hanaka, Hirotaka Ono, Kunihiko Sadakane +1
Given a directed edge-weighted graph with beer vertices , a beer path between two vertices and is a path between and that visits at least o…
On the Computational Complexity of Generalized Common Shape Puzzles
Mutsunori Banbara, Shin-ichi Minato, Hirotaka Ono +1
In this study, we investigate the computational complexity of some variants of generalized puzzles. We are provided with two sets S_1 and S_2 of polyominoes. The first puzzle asks…
Solving Distance-constrained Labeling Problems for Small Diameter Graphs via TSP
Tesshu Hanaka, Hirotaka Ono, Kosuke Sugiyama
In this paper, we give a simple polynomial-time reduction of {L(p)-Labeling} on graphs with a small diameter to {Metric (Path) TSP}, which enables us to use numerous results on {(M…
Grouped Domination Parameterized by Vertex Cover, Twin Cover, and Beyond
Tesshu Hanaka, Hirotaka Ono, Yota Otachi +1
A dominating set of graph is called an -grouped dominating set if can be partitioned into such that the size of each unit is and the s…
Sequentially Swapping Tokens: Further on Graph Classes
Hironori Kiya, Yuto Okada, Hirotaka Ono +1
We study the following variant of the 15 puzzle. Given a graph and two token placements on the vertices, we want to find a walk of the minimum length (if any exists) such that the…
Hedonic Seat Arrangement Problems
Hans L. Bodlaender, Tesshu Hanaka, Lars Jaffke +3
In this paper, we study a variant of hedonic games, called \textsc{Seat Arrangement}. The model is defined by a bijection from agents with preferences for each other to vertices in…
Computational Complexity of Hedonic Games on Sparse Graphs
Tesshu Hanaka, Hironori Kiya, Yasuhide Maei +1
The additively separable hedonic game (ASHG) is a model of coalition formation games on graphs. In this paper, we intensively and extensively investigate the computational complexi…
Independent Set Reconfiguration Parameterized by Modular-Width
Rémy Belmonte, Tesshu Hanaka, Michael Lampis +2
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 g…
Parameterized Complexity of Safe Set
Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis +3
In this paper we study the problem of finding a small safe set in a graph , i.e. a non-empty set of vertices such that no connected component of is adjacent to a larg…
Optimal Partition of a Tree with Social Distance
Masahiro Okubo, Tesshu Hanaka, Hirotaka Ono
We study the problem to find a partition of \textcolor{black}{a} graph with maximum social welfare based on social distance between vertices in , called MaxSWP. This problem…
Space-Efficient Algorithms for Longest Increasing Subsequence
Masashi Kiyomi, Hirotaka Ono, Yota Otachi +2
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 time and space. Our goa…
The complexity of dominating set reconfiguration
Arash Haddadan, Takehiro Ito, Amer E. Mouawad +4
Suppose that we are given two dominating sets and of a graph whose cardinalities are at most a given threshold . Then, we are asked whether there exists a sequen…
Subgraph Domatic Problem and Writing Capacity of Memory Devises with Restricted State Transitions
Tadashi Wadayama, Taizuke Izumi, Hirotaka Ono
A code design problem for memory devises with restricted state transitions is formulated as a combinatorial optimization problem that is called a subgraph domatic partition (subDP)…
Reconfiguration of Cliques in a Graph
Takehiro Ito, Hirotaka Ono, Yota Otachi
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-st…
Fixed-Parameter Tractability of Token Jumping on Planar Graphs
Takehiro Ito, Marcin Kamiński, Hirotaka Ono
Suppose that we are given two independent sets and of a graph such that , and imagine that a token is placed on each vertex in . The token jumping p…
(Total) Vector Domination for Graphs with Bounded Branchwidth
Toshimasa Ishii, Hirotaka Ono, Yushi Uno
Given a graph of order and an -dimensional non-negative vector , called demand vector, the vector domination (resp., total vector domina…
Coalescing random walks and voting on connected graphs
Colin Cooper, Robert Elsasser, Hirotaka Ono +1
In a coalescing random walk, a set of particles make independent random walks on a graph. Whenever one or more particles meet at a vertex, they unite to form a single particle, whi…
On the Approximability and Hardness of Minimum Topic Connected Overlay and Its Special Instances
Jun Hosoda, Juraj Hromkovic, Taisuke Izumi +3
In the context of designing a scalable overlay network to support decentralized topic-based pub/sub communication, the Minimum Topic-Connected Overlay problem (Min-TCO in short) ha…
Minimum Certificate Dispersal with Tree Structures
Taisuke Izumi, Tomoko Izumi, Hirotaka Ono +1
Given an n-vertex graph G=(V,E) and a set R \subseteq {{x,y} | x,y \in V} of requests, we consider to assign a set of edges to each vertex in G so that for every request {u, v} in…
A tight upper bound on the (2,1)-total labeling number of outerplanar graphs
Toru Hasunuma, Toshimasa Ishii, Hirotaka Ono +1
A -total labeling of a graph is an assignment from the vertex set and the edge set to the set of nonnegative integers such that $|f(x)-…
Deductive Inference for the Interiors and Exteriors of Horn Theories
Kazuhisa Makino, Hirotaka Ono
In this paper, we investigate the deductive inference for the interiors and exteriors of Horn knowledge bases, where the interiors and exteriors were introduced by Makino and Ibara…
A linear time algorithm for L(2,1)-labeling of trees
Toru Hasunuma, Toshimasa Ishii, Hirotaka Ono +1
An L(2,1)-labeling of a graph is an assignment from the vertex set to the set of nonnegative integers such that if and are adjacent and $|…