文献

J-GLOBAL ID：201902217573626461   整理番号：19A1787531

距離遺伝グラフ上の対支配問題【JST・京大機械翻訳】

Paired-Domination Problem on Distance Hereditary Graphs

著者 (4件)： Lin Ching-Chi (Department of Computer Science and Engineering, National Taiwan Ocean University, Keelung, Taiwan) ,  Ku Keng-Chu (Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan) ,  Chen Gen-Huey (Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan) ,  Hsu Chan-Hung (Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan)
資料名： Communications in Computer and Information Science  (Communications in Computer and Information Science)
巻： 1013  ページ： 495-502  発行年： 2019年 
JST資料番号： W5071A  ISSN： 1865-0929  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： グラフGのペア支配集合はGの支配集合Sであり,Sにより誘導されたGのサブグラフは完全な整合を持つ。「グラフ,ネットワーク,32:199-206,1998],HaynesおよびSlaterにおける[P通した domination]において,HaynesおよびSlaterは,paired-dominationの概念を導入し,最小のpaired-支配集合の決定問題が一般グラフ上でNP完全であることを示した。これまで,多くのアルゴリズム結果がグラフのいくつかの重要なクラスに関して研究されている。本論文では,距離遺伝グラフ上で[数式:原文を参照]時間アルゴリズムを提供することにより結果を拡張した。Copyright 2019 Springer Nature Singapore Pte Ltd. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 部分グラフ ,  決定問題 ,  ネットワーク ,  マッチング ,  *グラフ ,  *遺伝 ,  アルゴリズム
準シソーラス用語： NP完全性 ,  支配集合 , 【Automatic Indexing@JST】

著者キーワード (4件)： 対支配 ,  完全マッチング ,  距離遺伝グラフ ,  NP完全

分類 (1件)： グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (3件)： 遺伝 ,  グラフ ,  支配