抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
グラフGとcR:E(G)→[k]に対して,u,v|ΔV(G)間の経路Pは,明確なe,e→E(P)に対して,cR(e)≠cR(e′)を持つならば, rainbow経路である。Rainbow k-ColoringはグラフGを採り,その目的はcR:E(G)→[k]が全てのu,v→V(G)に対してuとvの間に rainbow経路が存在するかどうかをチェックすることである。上記の問題の2つのバリアントは,サブセットRainbow k-ColoringとSteiner Rainbow k-Coloringであり,ここでは,それぞれ,部分集合S≡V(G)×V(G)とS≡V(G)を付加的に与えた。さらに,その目的はcR:E(G)→[k]があるかどうかをチェックすることであり,それぞれ(u,v)∈Sとu,v∈S′に対する rainbow経路がある。ETHの下では,各k≧3:1に対して得られた。Rainbow k-Coloringは,2o(|E_(G)|)nO(1)-時間アルゴリズムを持たない。Steiner Rainbow k-Coloringは,2o(|S|2)nO(1)-時間アルゴリズムを持たない。また,Subset Rainbow k-ColoringおよびSteiner Rainbow k-Coloring admit 2O(|S|)nO(1)-および2O(|S|2)nO(1)-時間アルゴリズムを得た。Copyright 2022 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】
