Miyamoto Yuichiro

This paper discusses the problem of determining whether a given plane graph is a Delaunay graph, i.e., whether it is topologically equivalent to a Delaunay triangulation. There exist theorems which characterize Delaunay graphs and yield polynomial time algorithms for the problem only by solving some linear inequality systems. A polynomial time algorithm proposed by Hodgson, Rivin and Smith solves a linear inequality system given by Rivin, which is based on sophisticated arguments about hyperbolic geometry. Independently, Hiroshima, Miyamoto and Sugihara gave another linear inequality system and a polynomial time algorithm. Although their discussion is based on primitive arguments on Euclidean geometry, their proofs are long and intricate, unfortunately. In this paper, we give a simple proof of the theorem shown by Hiroshima et al. by employing the fixed point theorem.

This study uses a mathematical optimization approach to design safe walking routes from school to home for children. Children are thought to be safer when walking together in groups rather than alone. Thus, we assume that the risk of walking along a given road segment in a group is smaller than that of walking the same segment alone. At the same time, the walking route between school and home for each child should not deviate substantially from the shortest route. We propose a bi-objective model that minimizes both the total risk (particularly, the total distance walked alone) and the total walking distance for all children. We present an integer programming formulation of the proposed problem and apply this formulation to two instances based on actual road networks. We obtain Pareto optimal solutions using a mathematical programming solver and analyze the characteristics of the solutions and their potential applicability to real situations. The results show that the proposed model produces much better solutions compared with the solution where each child walks along the shortest path from school to home. In some optimal solutions, only a small deviation from the shortest path results in a dramatic reduction of the risk objective.

Modularity proposed by Newman and Girvan is a quality function for community detection. Numerous heuristics for modularity maximization have been proposed because the problem is NP-hard. However, the accuracy of these heuristics has yet to be properly evaluated because computational experiments typically use large networks whose optimal modularity is unknown. In this study, we propose two powerful methods for computing a nontrivial upper bound of modularity. More precisely, our methods can obtain the optimal value of a linear programming relaxation of the standard integer linear programming for modularity maximization. The first method modifies the traditional row generation approach proposed by Grotschel and Wakabayashi to shorten the computation time. The second method is based on a row and column generation. In this method, we first solve a significantly small subproblem of the linear programming and iteratively add rows and columns. Owing to the speed and memory efficiency of these proposed methods, they are suitable for large networks. In particular, the second method consumes exceedingly small memory capacity, enabling us to compute the optimal value of the linear programming for the Power Grid network (consisting of 4941 vertices and 6594 edges) on a standard desktop computer.