Journal of Information Processing 25(8) 695-707 2017年 [査読有り]
Hitori is a popular "pencil-and-paper" puzzle defined as follows. In n-hitori, we are given an n × n rectangular grid in which each square is labeled with a positive integer, and the goal is to paint a subset of the squares so that the following t...
INFORMATION PROCESSING LETTERS 116(9) 569-573 2016年9月 [査読有り]
We present a polynomial-time algorithm for solving SUBGRAPH ISOMORPHISM where the base graphs are bipartite permutation graphs and the pattern graphs are chain graphs. (C) 2016 Elsevier B.V. All rights reserved.
Many graph parameters of grid-like graphs are studied because of their algorithmic consequences. An important concept in this context is that of treewidth. Treewidth of graphs is a graph parameter for measuring how close a graph is to a tree. In t...