比較可能性有向グラフ:比較可能性グラフのアナログ【JST・京大機械翻訳】

Gao Xiao-Lu; Huang Jing; Xu Shou-Jun

プレプリント

J-GLOBAL ID：202202212448539808 整理番号：22P0324483

比較可能性有向グラフ:比較可能性グラフのアナログ【JST・京大機械翻訳】

Comparability digraphs: An analogue of comparability graphs

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

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

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

コンパラビリティグラフは一般的なクラスのグラフである。著者らは,比較可能グラフのクラスを比較可能グラフのダイグラフアナログとして導入した。含意クラスのような多くの概念と,比較可能グラフに対するノットグラフは,比較可能ダイグラフに自然に拡張できることを示した。著者らは,それらの結び目グラフに関して比較可能ダイグラフの特性評価を与えた。半完全比較可能ダイグラフは,比較可能ダイグラフのプロトタイプである。比較可能グラフの構造を解析するための1つの機器技術はグラフのための三角形Lemmaである。三角形Lemmaを半完全ダイグラフに一般化した。半完全ダイグラフに対するTriangle Lemmaを用いて,半完全ダイグラフの含意クラスが長さ2の回路を含まないならば,回路を全く含まないことを証明した。また,著者らは,nが入力ダイグラフの頂点の数である半完全比較可能ダイグラフのためのO(n ̄3)時間認識アルゴリズムにそれを使用した。アルゴリズムの正当性は,半完全比較可能ダイグラフのためのキャラクタリゼーションを意味し,比較可能グラフに対するそれと類似している。【JST・京大機械翻訳】

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

グラフ理論基礎 , 計算理論

, , ,

前のページに戻る