1-2hit |
Tatsuya GIMA Tesshu HANAKA Kohei NORO Hirotaka ONO Yota OTACHI
In this letter, we present a new lower bound for the treewidth of a graph in terms of the second smallest eigenvalue of its Laplacian matrix. Our bound slightly improves the lower bound given by Chandran and Subramanian [Inf. Process. Lett., 87 (2003)].
Tesshu HANAKA Nicolás HONORATO DROGUETT Kazuhiro KURITA Hirotaka ONO Yota OTACHI
In this paper, we study BALL COLLECTING WITH LIMITED ENERGY, which is a problem of scheduling robots with limited energy confined to a line to catch moving balls that eventually cross the line. For this problem, we show the NP-completeness of the general case and some algorithmic results for some cases with a small number of robots.