Hiro Ito

TCS Journal 2020 Journal Article

FUN editorial

• Hiro Ito
• Stefano Leonardi
• Linda Pagli
• Giuseppe Prencipe

TCS Journal 2013 Journal Article

The complexity of the stamp folding problem

• Takuya Umesato
• Toshiki Saitoh
• Ryuhei Uehara
• Hiro Ito
• Yoshio Okamoto

There are many folded states consistent with a given mountain–valley pattern of equidistant creases on a long paper strip. We would like to fold a paper strip such that the number of paper layers between each pair of hinged paper segments, called the crease width at the crease point, is minimized. This problem is called the stamp folding problem and there are two variants of this problem: minimization of the maximum crease width, and minimization of the total crease width. This optimization problem was recently introduced and investigated from the viewpoint of the counting problem. However, its computational complexity is not known. In this paper, we first show that the minimization problem of the maximum crease width is strongly NP-complete. Hence we cannot solve the problem in polynomial time unless P=NP. We next propose an algorithm that solves the minimization problem. The algorithm itself is a straightforward one, but its analysis is not trivial. We show that this algorithm runs in O ( ( k + 1 ) k n ) time where n is the number of creases and k is the total crease width.

STOC Conference 2009 Conference Paper

An improved constant-time approximation algorithm for maximum matchings

• Yuichi Yoshida
• Masaki Yamamoto 0001
• Hiro Ito

TCS Journal 2005 Journal Article

Single backup table schemes for shortest-path routing

• Hiro Ito
• Kazuo Iwama
• Yasuo Okabe
• Takuya Yoshihiro

We introduce a new recovery scheme that needs only one extra backup routing table for networks employing shortest-path routing. By precomputing this backup table, the network recovers from any single link failure immediately after the failure occurs. To compute the backup routing table for this scheme, we use an almost linear time algorithm to solve the { r, v } -problem, which is a variation of the best swap problem presented by Nardelli et al. We further show that the same solution can be computed in exactly linear time if the underlying graph is unweighted.