著者

Hironori KIYA Katsuki OHTO Hirotaka ONO

出版者

The Institute of Electronics, Information and Communication Engineers

雑誌

IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (ISSN:09168508)

巻号頁・発行日

pp.2020DMP0026, (Released:2021-02-10)

---

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.

著者

Yuta Harada Hirotaka Ono Kunihiko Sadakane Masafumi Yamashita

出版者

Information and Media Technologies Editorial Board

雑誌

Information and Media Technologies (ISSN:18810896)

巻号頁・発行日

vol.2, no.4, pp.1103-1112, 2007 (Released:2007-12-15)

参考文献数

9

---

The matching of a bipartite graph is a structure that can be seen in various assignment problems and has long been studied. The semi-matching is an extension of the matching for a bipartite graph G =(U ∪ V, E). It is defined as a set of edges, M ⊆ E, such that each vertex in U is an endpoint of exactly one edge in M. The load-balancing problem is the problem of finding a semi-matching such that the degrees of each vertex in V are balanced. This problem is studied in the context of the task scheduling to find a “balanced” assignment of tasks for machines, and an O(¦E¦¦U¦) time algorithm is proposed. On the other hand, in some practical problems, only balanced assignments are not sufficient, e.g., the assignment of wireless stations (users)to access points (APs) in wireless networks. In wireless networks, the quality of the transmission depends on the distance between a user and its AP; shorter distances are more desirable. In this paper, We formulate the min-weight load-balancing problem of finding a balanced semi-matching that minimizes the total weight for weighted bipartite graphs. We then give an optimal condition of weighted semi-matchings and propose an O(¦E¦¦U¦¦V¦) time algorithm.

著者

Kazuya HARAGUCHI Hirotaka ONO

出版者

The Institute of Electronics, Information and Communication Engineers

雑誌

IEICE TRANSACTIONS on Information and Systems (ISSN:09168532)

巻号頁・発行日

vol.E96-D, no.3, pp.481-488, 2013-03-01

---

BLOCKSUM, also known as KEISANBLOCK in Japanese, is a Latin square filling type puzzle, such as Sudoku. In this paper, we prove that the decision problem whether a given instance of BLOCKSUM has a solution or not is NP-complete.