Miyamoto Yuichiro

この記事は,オペレーションズ・リサーチの中でも特に組合せ最適化,あるいは離散アルゴリズムでよく用いられるグラフ理論の記法の手ほどきを目的としている.グラフ理論の記法では,集合や関数の使い方が重要である.よって,まず集合や関数についても少しだけ紹介した後に,グラフ理論の初歩を紹介する.そして,グラフ理論の記法の使い方の例として美術館定理を扱う.高校数学程度の論理的議論はできるがグラフ理論の数理的記述には慣れていないという読者を想定している.

In this paper, we present algorithms for channel (frequency) assignment problems. We formulate channel assignment problems as combinatorial optimization problems. We propose an exact method, an approximation algorithm and heuristic algorithms. We also report the results of computational experiences. We formulated the problem as an integer linear programming problem and applied a package software. We present a 5-approximation algorithm for particular graphs which are similar to real instances. We propose two construction methods and two improvement methods. Our heuristic algorithms are combinations of construction methods and improvement methods.

In this paper, we present algorithms for channel(frequency)assignment problems. We formulate channel assignment problems as combinatorial optimization problems. We propose an exact method, an approximation algorithm and heuristic algorithms. We also report the results of computational experiences. We formulated the problem as an integer linear programming problem and solved by a package software. We present a 5-approximation algorithm for particular graphs which are similar to real instances. We propose two construction methods and two improvement methods and present heuristic algorithms each of which is a combination of a construction method and improvement methods.