文献

J-GLOBAL ID：201502203016081458   整理番号：15A0259298

完全二部グラフと完全グラフのEuler回帰長の探求

The Quest for the Eulerian Recurrent Lengths of Complete Bipartite Graphs and Complete Graphs

著者 (1件)： JIMBO Shuji (Okayama Univ., Okayama, JPN)
資料名： Advanced Science Letters  (Advanced Science Letters)
巻： 20  号： 10/12  ページ： 2328-2333  発行年： 2014年10月 
JST資料番号： W2378A  ISSN： 1936-6612  資料種別： 逐次刊行物 (A)
記事区分： 短報  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 本論文は,完全二部グラフと完全グラフについてEuler回帰長問題(ERLP)を調査したものである。ERLPの目的は,Euler回路が与えられたグラフ内に存在するかどうかを決定することである。一方,ERLPはNP完全問題であり,さらにERLPに対して一定の近似率をもつ近似アルゴリズムは存在しないことが証明されている。著者らは,完全二部グラフと完全グラフのERLを調べ,その上で完全二部グラフのEuler回帰長の正確な値を求め,その正当性を証明した。また完全グラフのEuler回帰長について上界と下界を求め,その証明を説明した。著者らはグラフのERL見出すことが,他の最適化問題の解決有用であると期待している。

シソーラス用語： *部分グラフ ,  *完全グラフ ,  NP完全問題 ,  比率 ,  計算機アルゴリズム ,  最適化問題 ,  *グラフ理論
準シソーラス用語： *二部グラフ ,  近似アルゴリズム ,  近似率

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

タイトルに関連する用語 (3件)： 二部グラフ ,  完全グラフ ,  Euler