文献

J-GLOBAL ID：202002271705269946   整理番号：20A0791106

混合支配のための改良パラメータ化アルゴリズムとカーネル【JST・京大機械翻訳】

Improved parameterized algorithms and kernels for mixed domination

著者 (2件)： Xiao Mingyu (School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, China) ,  Sheng Zimo (School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, China)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 815  ページ： 109-120  発行年： 2020年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： グラフG=(V,E)の混合支配は,Dではない場合,頂点と頂点の混合集合Dであり,Dではなければ,それは隣接しているか,またはDにおいて少なくとも1つの頂点またはエッジに入射する。Mixed Domination問題は,グラフにおける大部分のkにおけるサイズの混合支配があるかどうかをチェックすることである。混合支配は頂点支配とエッジ支配の混合概念であり,混合支配問題を近似アルゴリズム,パラメータ化アルゴリズムなどの観点から研究した。本論文では,O*(7.465k)の以前の限界を改善するO*(4.172k)の実行時間限界を持つ分枝探索アルゴリズムを与えた。カーネル化のために,一般的グラフにおけるkによってパラメータ化された問題が多項式カーネルを持っていない可能性があることが知られている。平面グラフにおける問題は,11k-16頂点のカーネルを与えることにより線形カーネルを可能にすることを示した。Copyright 2020 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *多項式 ,  平面グラフ ,  線形性 ,  パラメタリゼーション
準シソーラス用語： グラフアルゴリズム ,  近似アルゴリズム ,  実行時間 ,  探索アルゴリズム ,  *パラメータ化アルゴリズム ,  カーネル化 , 【Automatic Indexing@JST】

著者キーワード (5件)： パラメータ化アルゴリズム ,  混合支配 ,  グラフアルゴリズム ,  カーネル化 ,  分岐と探索

分類 (2件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

タイトルに関連する用語 (3件)： 支配 ,  パラメータ化アルゴリズム ,  カーネル