文献

J-GLOBAL ID：202002235978484460   整理番号：20A2193922

グラフの3種類のカラー接続に対する硬度結果【JST・京大機械翻訳】

Hardness results for three kinds of colored connections of graphs

著者 (2件)： Huang Zhong (Center for Combinatorics and LPMC, Nankai University, Tianjin 300071, China) ,  Li Xueliang (Center for Combinatorics and LPMC, Nankai University, Tianjin 300071, China)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 841  ページ： 27-38  発行年： 2020年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： グラフの rainbow結合数の概念を2008年にChartrandらによって導入した。この概念に触発されて,2011年のCaroとYusterによる単色接続数,2012年のBorozanらによる適切な接続数,および2018年のCzapらによるコンフリクトフリー接続数,および後の接続数のいくつかの他のバリアントなど,グラフにおける連結性の有色バージョンに関する他の概念を紹介した。Chakrbortyらは,グラフの rainbow結合数を計算することがNP困難であることを証明した。長い間,単色接続数,適切な接続数およびグラフの無衝突接続数に対する計算量を固定することを試みた。しかし,まだ解決されていない。強いバージョン,すなわち,強い適切な接続数および強い無衝突接続数に対する複雑性結果のみ,これらの接続数の数値はNP困難であると決定された。本論文では,単色接続数のそれぞれを計算するため,グラフに対する適切な接続数と衝突自由接続数はNP困難であることを証明した。これは,この分野での長い定住問題を解決し,ワークショップと論文の多くの会話に依頼した。Copyright 2020 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  計算量 ,  硬度 ,  連結性 ,  *NP困難
準シソーラス用語： 有彩色 ,  複雑性 ,  単色 , 【Automatic Indexing@JST】

著者キーワード (6件)： 単色接続数 ,  適切な接続数 ,  矛盾のない接続数 ,  複雑性 ,  NP困難 ,  アルゴリズム

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

タイトルに関連する用語 (3件)： グラフ ,  カラー ,  硬度