2 citations · 2 across the 4 of their papers we have counts for
4 papers
Hardness of Forcing Unique Perfect Matchings in Bipartite Graphs of Maximum Degree 3
Ryoma Aoshima, Takashi Horiyama, Atsuki Nagao +4
In a graph , a set of edges is called a \emph{forcing set} if there exists a unique perfect matching such that . Similarly, a set of edges is called a…
Meta Theorem for Hardness on FCP-Problem
Atsuki Nagao, Mei Sekiguchi
The Fewest Clues Problem (FCP) framework has been introduced to study the complexity of determining whether a solution to an \NP~problem can be uniquely identified by specifying a…
On the complexity of finding a spanning even tree in a graph
Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita +4
A tree is said to be even if for every pair of distinct leaves, the length of the unique path between them is even. In this paper we discuss the problem of determining whether an i…
Feedback game on Eulerian graphs
Naoki Matsumoto, Atsuki Nagao
In this paper, we introduce a two-player impartial game on graphs, called a {\em feedback game}, which is a variant of the generalized geography. We study the feedback game on Eule…