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…