せいぜい8つのノードを有するすべてのグラフは2-間隔-PCGである。【JST機械翻訳】

Calamoneri Tiziana; Monti Angelo; Petroni Fabrizio

プレプリント

J-GLOBAL ID：202202220019710933 整理番号：22P0296456

せいぜい8つのノードを有するすべてのグラフは2-間隔-PCGである。【JST機械翻訳】

All Graphs with at most 8 nodes are 2-interval-PCGs

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

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

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

グラフGは,もしGの各ノードがTの葉に一意的に付随し,もしTにおけるそれらの対応する葉の間の重み付き距離が任意のそのような区間内にある場合に限り,Gの中の2つのノード間にエッジが存在するような非負実値を持つエッジ重み付きツリーTおよび非負実ハーフラインの互いに素な区間が存在するならば,多重区間PCGである。間隔の数がkであるならば,グラフをk間隔PCGと呼ぶ。記号では,G=k間隔PCG(T,I_1,...,I_k)である。2区間PCGは全てのグラフを含まず,このクラスの外の最小既知グラフは135ノードを持つことが知られている。ここでは,高々8ノードを持つすべてのグラフが2区間PCGであり,2区間PCGではないnノードグラフが存在するようなnの最小値の決定に向けて1ステップを行うことであることを証明した。【JST機械翻訳】

, , ,
, 【Automatic Indexing@JST】

グラフ理論基礎 , その他のオペレーションズリサーチの手法

, ,

前のページに戻る