文献

J-GLOBAL ID：201902247568252119   整理番号：19A1792812

区間グラフの最小kホップ支配集合を発見するための最適アルゴリズム【JST・京大機械翻訳】

An optimal algorithm to find minimum k-hop dominating set of interval graphs

著者 (3件)： Barman Sambhu Charan (Department of Mathematics, Shahid Matangini Hazra Govt. College for Women, Nimtouri, Tamluk, Purba Medinipur 721649, India) ,  Pal Madhumangal (Department of Applied Mathematics with Oceanology and Computer Programming, Vidyasagar University, Midnapore 721102, India) ,  Mondal Sukumar (Department of Mathematics, Raja N. L. Khan Women’s College, Gope Palace, Midnapore 721102, India)
資料名： Discrete Mathematics, Algorithms and Applications  (Discrete Mathematics, Algorithms and Applications)
巻： 11  号： 2  ページ： 1950016  発行年： 2019年 
JST資料番号： W3711A  ISSN： 1793-8309  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： シンガポール (SGP)  言語： 英語 (EN)

抄録/ポイント： 固定された正の整数kに対して,グラフ[数式:原文を参照]のk-ホップ支配集合Dは,各頂点[数式:原文を参照]が少なくとも1つの頂点[数式:原文を参照],すなわち,[数式:原文を参照]からk-ステップ内にあるようなVの部分集合である。k-ホップ支配集合Dは,[数式:原文を参照]がGのk-ホップ支配集合であるようないかなる[数式:原文を参照]も存在しない場合には最小であると言われている。支配的集合Dは最小kホップ支配集合であると言われているが,それはkホップ支配集合と同様に最小である。本論文では,[数式:原文を参照]時間で実行するn頂点を持つ区間グラフの最小kホップ支配集合を見出すための最適アルゴリズムを示した。Copyright 2019 World Scientific Publishing Company All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *グラフ ,  部分集合
準シソーラス用語： *最適アルゴリズム ,  *支配集合 ,  *区間グラフ , 【Automatic Indexing@JST】

著者キーワード (4件)： アルゴリズムの設計 ,  アルゴリズムの解析 ,  kホップ支配 ,  区間グラフ

分類 (2件)： 集合論  (AB10000I) ,  グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (5件)： 区間グラフ ,  ホップ ,  支配集合 ,  発見 ,  最適アルゴリズム