平行な2直線上のdispersion問題

田中 優輝  宮田 洋行  中野 眞一  

誌名
電子情報通信学会論文誌 A   Vol.J105-A    No.1    pp.1-5
発行日: 2022/01/01
早期公開日: 2021/07/30
Online ISSN: 1881-0195
DOI: 10.14923/transfunj.2021JAP1005
論文種別: 論文
専門分野: アルゴリズムとデータ構造・計算複雑度
キーワード: 
施設配置問題,  Dispersion問題,  アルゴリズム,  

本文: PDF(13.3MB)>>
論文を購入



あらまし: 
点集合Pと整数kが与えられたとき,施設間の最小距離が最大になるようにP中のk点に施設を配置したい.この問題をdispersion問題という.dispersion問題は一般にNP困難である.本論文は,Pが平行な2直線上にあるとき,この問題を解く,効率的なアルゴリズムを設計する.