Miyamoto Yuichiro

In this paper, we propose the levelwise mesh sparsification method for the shortest path query problem. Several sparse networks are obtained by sparsifying the original network, and the shortest path problem is solved by finding the shortest path in these networks. The obtained networks are sparse and small, thus the computational time is short. Computational experiments on real world data show the efficiency of our method in terms of computational time and memory efficiency. Compared with existing approaches, the advantage of our method is that it can deal with negative costs and time-dependent costs, and uses only a small amount of memory.

Given a pair of non-negative integers m and n, P(m, n) denotes a subset of 2-dimensional triangular lattice points defined by P(m, n)={(ze_1+ye_2)|x∈{0,1,…,m-1},y∈{0,1,…,n-1 } } where e_1=^^<def>(1,0),e_2=^^<def>(1/2,√<3>/2). Let T_<m, n>(d) be an undirected graph defined on vertex set P(m, n) satisfying that two vertices are adjacent if and only if the Euclidean distance between the pair is less than or equal to d. In this paper, we discuss a necessary and sufficient condition that T_<m, n>(d) is perfect. More precisely, we show that ∀m∈Z_+, T_<m, n>(d) is perfect ] if and only if d≧√<n^2-3n+3>. Given a non-negative vertex weight vector ω∈Z^<P(m, n)>_+, a multicoloring of (T_<m, n>(d),ω) is an assignment of colors to P(m, n) such that each vertex υ∈P(m, n) admits ω(υ) colors and every adjacent pair of two vertices does not share a common color. We also give an efficient algorithm for muliticoloring (T_m, n(d), ω) when P(m, n) is perfect. In general case, our results on the perfectness of P(m, n) implies a polynomial time approximation algorithm for multicoloring (T_m, n(d), ω). Our algorithm finds a multicoloring which uses at most α(d)ω+O(d^3) colors, where ω denotes the weighted clique number. When d=1, √<3>, 2,√<7>, 3, the approximation ratio α(d)=(4/3), (5/3), (5/3), (7/4), (7/4), respectively. When d>1, we showed that α(d)≦(1+2/√<3>+(√^2<3>-3)/d). We also showed the NP-completeness of the problem to determine the existence of a multicoloring of (T_m, n(d), ω) with strictly less than (4/3)ω colors.