<i>k</i>-cyclic Orientations of Graphs

• Item type: SIG Technical Reports(1)
• 公開日: 2011-02-28
• タイトル: <i>k</i>-cyclic Orientations of Graphs
• タイトル / 言語: en
• タイトル: <i>k</i>-cyclic Orientations of Graphs
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Graduate School of Science and Technology, Meiji University.
• 著者所属: Department of Information and Communication Sciences, Faculty of Science and Technology, Sophia University.
• 著者所属: Department of Computer Science, Meiji University.
• 著者所属(英): en
• 著者所属(英): Graduate School of Science and Technology, Meiji University.
• 著者所属(英): en
• 著者所属(英): Department of Information and Communication Sciences, Faculty of Science and Technology, Sophia University.
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Meiji University.
• 著者名: Yasuaki, Kobayashi; Yuichiro, Miyamoto; Hisao, Tamaki
• 著者名(英): Yasuaki, Kobayashi; Yuichiro, Miyamoto; Hisao, Tamaki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: An orientation of an undirected graph G is a directed graph, with same vertex set, whose underlying graph is G. For integer k ≥ 3, we say a directed graph D is k-cyclic if every edge of D belongs to a directed cycle in D of length at most k. We consider the problem of deciding if a given graph has a k-cyclic orientation. We show that this problem is NP-complete for every fixed k ≥ 3 for general graphs and for every fixed k ≥ 4 for planar graphs. We give a polynomial time algorithm for planar graphs with k = 3, which constructs a 3-cyclic orientation when the answer is affirmative.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: An orientation of an undirected graph G is a directed graph, with same vertex set, whose underlying graph is G. For integer k ≥ 3, we say a directed graph D is k-cyclic if every edge of D belongs to a directed cycle in D of length at most k. We consider the problem of deciding if a given graph has a k-cyclic orientation. We show that this problem is NP-complete for every fixed k ≥ 3 for general graphs and for every fixed k ≥ 4 for planar graphs. We give a polynomial time algorithm for planar graphs with k = 3, which constructs a 3-cyclic orientation when the answer is affirmative.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2011-AL-134, 号 6, p. 1-8, 発行日 2011-02-28
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会