文献

J-GLOBAL ID：201802253620106047   整理番号：18A0236811

部分有向グラフの配向を完成させる【Powered by NICT】

Completing orientations of partially oriented graphs

著者 (3件)： Bang-Jensen J. (Department of Mathematics and Computer Science, University of Southern Denmark, Odense DK-5230, Denmark) ,  Huang J. (Department of Mathematics and Statistics, University of Victoria, Victoria, BC V8W 3R4, Canada) ,  Zhu X. (Department of Mathematics, Zhejiang Normal University, Jinhua, China)
資料名： Journal of Graph Theory  (Journal of Graph Theory)
巻： 87  号： 3  ページ： 285-304  発行年： 2018年 
JST資料番号： C0773B  ISSN： 0364-9024  CODEN： JGTHD  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： の配向完成問題と呼ぶ一般的な研究を開始した。有向グラフの固定クラスCに対して,配向完成問題は,与えられた部分的に配向したグラフPは一般的に,特定クラスグラフと有向グラフの認識を含むいくつかの既存問題を一般化したP.配向完成問題における(無方向性)エッジ配向と同様にある種の幾何学的表現可能なグラフの表現を拡張してCにおける有向グラフに完了することができるかどうかを問う。種々クラス有向グラフの配向完成問題,有向サイクル因子を持っていることがKアーク強い有向グラフ,k強い有向グラフ,準推移配向グラフ,局所トーナメント,非環式局所トーナメント,局所的に推移的トーナメント,局所推移局所トーナメント,トーナメント,有向グラフを含むを研究した。がこれらのクラスのそれぞれに対して配向完成問題は多項式時間で解けるまたはNP完全であることを示した。も入力指向グラフがある追加条件を満たす場合NP完全問題のいくつかは,多項式時間で解けることを示した。著者らの結果は,適切な区間グラフと適切な円弧グラフの表現拡張問題は多項式時間で解けることを意味している。後者は以前の結果を一般化した。Copyright 2018 Wiley Publishing Japan K.K. All Rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： *グラフ ,  円弧 ,  指向性 ,  NP完全問題 ,  アーク放電 ,  *有向グラフ
準シソーラス用語： 多項式時間アルゴリズム ,  区間グラフ ,  NP完全性 ,  多項式時間 ,  トーナメント , 【Automatic Indexing@JST】

著者キーワード (12件)： に優しい部分配向グラフ ,  におけるトーナメント ,  局所トーナメント ,  局所推移的局所トーナメント ,  NP完全 ,  配向完成問題 ,  部分的に配向したグラフ ,  多項式時間アルゴリズム ,  適切な円弧グラフ ,  適切な区間グラフ ,  recognition ,  表現拡張

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

タイトルに関連する用語 (2件)： 有向グラフ ,  配向