区間ハイパーグラフの強い矛盾のない彩色の完全分解能【JST・京大機械翻訳】

Dhannya S. M.; Narayanaswamy N. S.

プレプリント

J-GLOBAL ID：202202214954045280 整理番号：21P0004702

区間ハイパーグラフの強い矛盾のない彩色の完全分解能【JST・京大機械翻訳】

Perfect Resolution of Strong Conflict-Free Colouring of Interval Hypergraphs

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

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

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

k-Strong Conflict-Free(k-SCF,略して)彩色問題は,Hのあらゆるハイパーエッジeにおいて,カラーがeの他のすべての頂点のものと異なる最小数分|,k}頂点があるように,色の最小数を用いてハイパーグラフHの頂点の彩色を見つけるのを追求する。間隔超グラフの場合,k-SCF問題に対する正確なP-時間アルゴリズムを提示し,Cheilarisら(2014)によって提起された未解決問題を解決した。任意のハイパーグラフに対して,k-SCF彩色は,共起グラフとして参照される関連単純グラフの適切な彩色であることを,著者らは示した。次に,共起グラフを,著者らが導入した第2の簡単なグラフの誘起部分グラフを同定することによって得,著者らは,衝突グラフとして言及する。間隔超グラフに対して,各共起グラフとコンフリクトグラフが完全グラフであることを示した。この特性は,多項式時間アルゴリズムにおいて重要な役割を果たす。第2に,区間超グラフに対して,1SCF彩色数は,各集合が正確なヒット集合(各間隔が一度にヒットするヒット集合)を持つような集合へのその間隔の最小分割であることを示した。【JST・京大機械翻訳】

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

グラフ理論基礎 , 集合論

, , ,

前のページに戻る