宮本 裕一郎

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.

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.

This paper considers an auction-based scheduling system in a job shop equipped with ubiquitous network environment to cope with dynamically changing market demands. Under such environment all machines and jobs are assumed to have computing and communication devices and can serve as intelligent agents. The functions for an auctioneer and for a participant are investigated to install the scheduling system as a distributed multi-agent system. The systems sending and receiving messages for the auction form a distributed system on a network, enabling an autonomous scheduling.

An orientation of an undirected graph G is a directed graph D on V(G) with exactly one of directed edges (u, v) and (vu) for each pair of vertices u and v adjacent in G. For integer k >= 3, we say a directed graph D is k-cyclic if every edge of D belongs to a directed cycle in D of length at most k. We consider the problem of deciding if a given graph has a k-cyclic orientation. We show that this problem is NP-complete for every fixed k >= 3 for general graphs and for every fixed k >= 4 for planar graphs. We give a polynomial time algorithm for planar graphs with k = 3, which constructs a 3-cyclic orientation when the answer is affirmative.

In this paper, we address the shortest path query problem, i.e., constructing a data structure of a given network to answer the shortest path length of two given points in a short time. We present a method named Levelwise Mesh Sparsification for the problem. The key idea is to divide the network into meshes and to sparsify the network in each mesh by removing unnecessary edges and vertices that are never used when the shortest path passes through the mesh. In large real-world road networks in the United States, our method is about 1,500 times faster than Dijkstra's algorithm, which is competitive with existing methods. The time taken to construct the data structure is a few hours on a typical PC. Unlike previous methods, our geometric partition method succeeded in reducing the data for connecting the sparsified network. As a result, our method uses additional data that is only about 10% of the original data size, while existing methods use more than 2000%. Our method has considerable extensibility because it is independent of search algorithms. Thus, it can be used with Dijkstra's algorithm and A*-search among others, and with several models such as negative costs, time-dependent costs, and so on. These are rarely handled by previous methods.

Given a finite set of 2-dimensional points P c R 2 and a positive real d, a unit disk graph, denoted by (P. d), is an undirected graph with vertex set P such that two vertices are adjacent if and only if the Euclidean distance between the pair is less than or equal to d. 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) (def) double under bar {(xe(1) + ye(2)) vertical bar x is an element of {0, 1, . . . , m - 1}, y is an element of {0, 1, . . . , n - 1 } } where e(1) (def) double under bar (1, 0), e(2) (def) under bar (1/2, root-3/2). Let T(m,n)(d) be a unit disk graph defined on a vertex set P(m, n) and a positive real d. Let T(m,n)(k) be the kth power of T(m,n)(1). In this paper, we show necessary and sufficient conditions that [for all m, T(m,n)(d) is perfect] and/or [for all m, T(m,n)(k) is perfect], respectively. These conditions imply polynomial time approximation algorithms for multicoloring (T(m,n)(d), w) and (T(m,n)(k), w). (C) 2008 Elsevier B.V. All rights reserved.

Given an undirected and edge-weighted graph G together with a set of ordered vertex-pairs, called st-pairs, we consider the problems of finding an orientation of all edges in G: MIN-SUM ORIENTATION is to minimize the sum of the shortest directed distances between all st-pairs; and MIN-MAX ORIENTATION is to minimize the maximum shortest directed distance among all st-pairs. In this paper, we first show that both problems are strongly NP-hard for planar graphs even if all edge-weights are identical, and that both problems can be solved in polynomial time for cycles. We then consider the problems restricted to cacti, winch form a graph class that contains trees and cycles but is a subclass of planar graphs. Then, MIN-SUM ORIENTATION is solvable in polynomial time, whereas MIN-MAX ORIENTATION remains NP-hard even for two st-pairs. However, based on LP-relaxation, we present a polynomial-tine 2-approximation algorithm for MIN-MAX ORIENTATION. Finally, we give a fully polynomial-time approximation scheme (FPTAS) for MIN-MAX ORIENTATION on cacti if the number of st-pairs is a fixed constant.

本論文では最短路を高速に検索するためのデータ構造とアルゴリズムの工夫，階層メッシュ疎化法，を提案する．最短路に頻出する枝をあらかじめ抽出することで，応答する経路の最適性を保証しつつ，検索時間の大幅な短縮に成功した．全米道路（約 2400 万点，約 5800 万枝）に適用した実験結果も報告する．階層メッシュ疎化法は，関連する既存手法に比べてメモリ使用量が少ないのが長所である．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.

We propose polynomial time approximation algorithms for minimum span channel (frequency) assignment problems, which is known to be NP-hard. Let alpha be the approximation ratio of our algorithm and W >= 2 be the maximum of numbers of channels required in vertices. If an instance is defined on a perfect graph G, then alpha <= 1 + (1 + 1/W-1) H-omega((G)), where Hi denotes the i-th harmonic number. For any instance defined on a unit disk graph G, alpha is less than or equal to (1 + 1/w-1)(3H(omega)((G))-1). If a given graph is 4 or 3 colorable, a is bounded by (2.5 + W-1 (2 + 1/W-1), respectively. We also discuss well-known practical instances called, Philadelphia instances and propose an algorithm with alpha < 12/5.

Given a pair of non-negative integers m and n, P(m, a) denotes a subset, of 2-dimensional triangular lattice points defined by P(m, n) (def) double under bar. {(xe(1) + ye(2)) vertical bar x is an element of {0, 1, ... , m - 1} y is an element of {0, 1, ... , n - 1 } } where e(1) (def) double under bar. (1, 0), e(2) (def) double under bar. (1/2, root 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. This paper discusses a necessary and sufficient condition that T(m,n)(d) is perfect; we show that [for all m is an element of Z(+), T(m,n)(d) is perfect] if and only if d >= root n(2)-3n+3. Given a non-negative vertex weight. vector w is an element of Z(+)(P(m, n)), a multicoloring of (T(m,n)(d), w) is an assignment, of colors to P(m, n) such that each vertex v is an element of P(m, n) admits w(v) colors and every adjacent pair of two vertices does not share a common color. We also give an efficient algorithm for multicoloring (T(m,n) (d), w) 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), w). Our algorithm finds a multicoloring which uses at most alpha(d)omega + O(d(3)) colors, where w denotes the weighted clique number. When d = 1, root 3, 2, root 7, 3, the approximation ratio alpha(d) = (4/3), (5/3), (5/3), (7/4), (7/4), respectively. When d > 1, we showed that alpha(d) <= (1 + 2/root 3-1 2 root 3-3/d) < 1 + 2/root 3 < 2.155.

Given a pair of non-negative integers m and n, S(m,n) denotes a square lattice graph with a vertex set {0, 1, 2, ..., m - 1} x {0, 1, 2, ..., n - 1}, where a pair of two vertices is adjacent if and only if the distance is equal to 1. A triangular lattice graph T(m, n) has a vertex set {(xe(1) + ye(2)) | x is an element of {0, 1, 2, ..., m - 1}, y is an element of {0, 1, 2, ..., n - 1 } } where e(1)(def) = (1, 0), e(2)(def) = (1/2, root 3/2), and an edge set consists of a pair of vertices with unit distance. Let S-k (m, n) and T-k (m, n) be the kth power of the graph S(m, n) and T(m, n), respectively. Given an undirected graph G = (V, E) and a non-negative vertex weight function w : V -> Z(+), a multicoloring of G is an assignment of colors to V such that each vertex v is an element of V admits w(v) colors and every adjacent pair of two vertices does not share a common color. In this paper, we show necessary and sufficient conditions that [for all m, the S-k(m,n) is perfect] and/or [for all m, T-k(m,n) is perfect], respectively. These conditions imply polynomial time approximation algorithms for multicoloring (S-k(m,n),w) and (T-k(m,n),w).

与えられた非負整数mとnに対して，P(m n)def.＝{(xe_1+ye_2)ｌx∈{0 1 ... m?1} y∈{0 1 ... n-1 } }と定義する．ここでe_1def.＝(1 0) e_2def.＝(1/2 √3/2)である，つまりP(m n)は2次元平面上の三角格子点の部分集合を表す．P(m n)を頂点集合とし，頂点間のユークリッド距離がd以下であるときに隣接と定義する無向グラフをT_m n(d)とする．本稿ではT_m n(d)がパーフェクトであるための必要条件と十分条件を議論する．具体的には，∀m∈Z_＋に対してT_m n(d)がパーフェクトである必要十分条件はd≧√n^2-√3n+√3であることを示す．非負整数頂点重みw∈Z^p(m n) _＋が与えられたとき，それぞれの頂点υ∈P(m n)にω(υ)色が割り当てられ，隣接するどの頂点対も同じ色を共有しないようなP(m n)への色の割り当てを(T_m n(d) ω)の多重彩色という．本稿ではP(m n)がパーフェクトであるときに(T_m n(d) ω)を多重彩色する効率的な算法も示す．本稿の主な成果であるP(m n)のパーフェクト性を利用すると一般の(T_m n(d) ω)の多重彩色に対する多項式時間精度保証付き近似解法を構成できる．こうして構成した算法は高々α(d)ω＋ο(d^3)色を用いた多重彩色の解を算出する．ここでωは重み付きクリーク数である．d＝1 √3 2 √7 3のとき，対応する近似率α(d)はそれぞれ(4/3) (5/3) (5/3) (7/4) (7/4)である．d＞1のときα(d)≦(1＋2/√3＋2√3-3/d)である．また本稿では，(T_m n(d) ω)を(4/3)ω色で多重彩色できるか否か判定する問題はNP-完全であることを示す．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) def.＝{(xe_1+ye_2)ｌx∈{0,1,...,m竏驤1,y∈{0,1,...,n-1 } }where e_1 def.＝(1,0),e2 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_+, Tm,n(d) is perfect ] if and only if d≧√n^2-√3n+√3. Given a non-negative vertex weight vector w∈Z^p(m,n) _＋, a multicoloring of (Tm,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 (Tm,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 (Tm,n(d),ω). Our algorithm finds a multicoloring which uses at most α(d)ω＋ο(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 (Tm,n(d),ω) with strictly less than (4/3)ω colors.

This paper is concerned with the input-or-output test that is a kind of interval capacity consistency tests. And an O(n(2) log(2) n) algorithm dealing with the test is proposed, where n denotes the number of jobs. In literature, an O(n(4)) algorithm has been known. The tests can be effectively used to reduce the search space of time- and resource-constrained scheduling problems. Computational results show that our new algorithm is about 3 times faster for instances of 30 jobs than the existing algorithm.

Let P be a subset of 2-dimensional integer lattice points P = {1,2,... m} x {1,2,...,n} subset of or equal to Z(2). We consider the graph G(p) with vertex set P satisfying that two vertices in P are adjacent if and only if Euclidean distance between the pair is less than or equal to root2. Given a non-negative vertex weight vector w is an element of Z(+)(P), a multicoloring of (G(p), w) is an assignment of colors to P such that each vertex v is an element of P admits w(v) colors and every adjacent pair of two vertices does not share a common color. We show the NP-completeness of the problem to determine the existence of a multicoloring of (G(p), w) with strictly less than (4/3)w colors where w denotes the weight of a maximum weight clique. We also propose an O(mn) time approximation algorithm for multicoloring (G(p), w). Our algorithm finds a multicoloring with at most (4/3)w + 4 colors Our algorithm based on the property that when n = 3, we can find a multicoloring of (G(p), w) with W colors easily, since an undirected graph associated with (G(p), w) becomes a perfect graph.

We consider the item assortment problem of a vending machine. Our goal is to determine the optimal assortment of items and the optimal replenishment cycle time of the vending machine. We model the problem as mathematical programming problems. We formulate this problem as an integer linear programming problem to get tight lower bounds and apply the column generation method for its linear relaxation problem. We also propose two algorithms to get upper bounds, one based on tabu search and the other on multiple start local search. Our numerical experiments on a real world instance and randomly generated instances show that our methods generate good solutions within a reasonable computational time.

This paper presents a new proof to polynomial-time algorithm for determining whether a given embedded graph is a Delaunay graph, i.e., whether it is topologically equivalent to a Delaunay triangulation. The problem of recognizing the Delaunay graph had long been open. Recently Hodgson et al. gave a combinatorial characterization of the Delaunay graph, and thus constructed the polynomial-time algorithm for recognizing the Delaunay graphs. Their proof is based on sophisticated discussions on hyperbolic geometry. On the other hand, this paper gives another and simpler proof based on primitive arguments on Euclidean geometry. Moreover, the algorithm is applied to study the distribution of non-Delaunay graphs.