グラフモザイクカバー数:極値限界,効率的なアルゴリズムおよび硬度【JST・京大機械翻訳】

Abreu A.; Cunha L.; Fernandes T.; de Figueiredo C.; Kowada L.; Marquezino F.; Posner D.; Portugal R.

プレプリント

J-GLOBAL ID：202202216608951684 整理番号：21P0005782

グラフモザイクカバー数:極値限界,効率的なアルゴリズムおよび硬度【JST・京大機械翻訳】

The graph tessellation cover number: extremal bounds, efficient algorithms and hardness

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (8件)： , , , , , , ,
資料名：
発行年： 2017年12月20日プレプリントサーバーでの情報更新日： 2017年12月20日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

※このプレプリント論文は学術誌に掲載済みです。なお、学術誌掲載の際には一部内容が変更されている可能性があります。

グラフの分割はその頂点分割クリークへの分割である。グラフのモザイクカバーは,そのエッジの全てをカバーするモザイクの集合である。t-テッセルラビリティ問題は,t分割によるグラフのモザイク被覆があるかどうかを決定することを目的とする。この問題は,量子ウォークモデルへの応用により動機づけられ,特に,スタガードモデルの進化演算子はグラフモザイクカバーから得られる。グラフの彩色指数とクリークグラフの彩色数の間の最小によって与えられるモザイクカバー数に関する上限を確立して,著者らはこれらの限界が緊密であるグラフクラスを示した。インスタンスが平面グラフ,弦(2,1)グラフ,(1,2)グラフ,直径5のダイヤモンドフリーグラフ,あるいは少なくとも3の任意の固定tに対して制約された場合,t-テスタビリティに対するNP完全性を証明した。他方では,線形時間アルゴリズムに対する2テセルラビリティに対する複雑性を改善した。【JST・京大機械翻訳】

, , , , , , ,
, , , , , 【Automatic Indexing@JST】

グラフ理論基礎

, , ,

前のページに戻る