JAIST Repository >
b. 情報科学研究科・情報科学系 >
b10. 学術雑誌論文等 >
b10-1. 雑誌掲載論文 >

このアイテムの引用には次の識別子を使用してください: http://hdl.handle.net/10119/10887

タイトル: On bipartite powers of bigraphs
著者: Okamoto, Yoshio
Otachi, Yota
Uehara, Ryuhei
キーワード: bipartite power
interval bigraph
bipartite permutation graph
closure property
NP-completeness
発行日: 2012
出版者: Discrete Mathematics and Theoretical Computer Science
誌名: Discrete Mathematics and Theoretical Computer Science
巻: 14
号: 2
開始ページ: 11
終了ページ: 20
抄録: The notion of graph powers is a well-studied topic in graph theory and its applications. In this paper、 we investigate abipartite analogue of graph powers、 which we call bipartite powers of bigraphs. We show that the classes of bipartitepermutation graphs and interval bigraphs are closed under taking bipartite power. We also show that the problem ofrecognizing bipartite powers is NP-complete in general.
Rights: Copyright (C) 2012 Discrete Mathematics and Theoretical Computer Science. Yoshio Okamoto, Yota Otachi, and Ryuhei Uehara, Discrete Mathematics and Theoretical Computer Science, 14(2), 2012, 11-20.
URI: http://hdl.handle.net/10119/10887
資料タイプ: publisher
出現コレクション:b10-1. 雑誌掲載論文 (Journal Articles)

このアイテムのファイル:

ファイル 記述 サイズ形式
18420.pdf350KbAdobe PDF見る/開く

当システムに保管されているアイテムはすべて著作権により保護されています。

 


お問い合わせ先 : 北陸先端科学技術大学院大学 研究推進課図書館情報係