電波による通信を用いたサービスでは、基地局の通信の範囲は円となる.複数の基地局からの通信が重なることで不具合がでる場合もあり,どのように基地局を配置するかが問題になる.ここでサービスの利用者を点,電波の届く範囲を単位円としたときに,重なりの無い単位円集合ですべての点を覆えるか,という問題が考えられる.本研究では,これを複数の単位円による点集合の排他的被覆問題として取り扱う.どのように配置しても必ず適当に配置した単位円の集合で排他的に被覆できる点の個数 k は 1 以上で上限があり,既知の結...
The graph reconstruction conjecture is a long-standing open problem in graph theory. There are many algorithmic studies related to it, such as DECK CHECKING, LEGITIMATE DECK, PREIMAGE CONSTRUCTION, and PREIMAGE COUNTING. We study these algorithmic...
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS E93D(7) 1816-1823 2010年7月 [査読有り]
We investigate connected proper interval graphs without vertex labels. We first give the number of connected proper interval graphs of n vertices. Using this result, a simple algorithm that generates a connected proper interval graph uniformly at ...
We discuss the problems to list, sample, and count the chordal graphs with edge constraints. The objects we look at are chordal graphs sandwiched by a given pair of graphs where we assume that at least one of the input graphs is chordal. The setti...