Bipartite powers of interval bigraphs
スポンサーリンク
概要
- 論文の詳細を見る
The notion of graph powers is a well-studied topic in graph theory and its applications. In this paper, we investigate a bipartite analogue of graph powers, which we call bipartite powers of bigraphs. We show that the classes of bipartite permutation graphs and interval bigraphs are closed under taking bipartite power. We also show that the problem of recognizing bipartite powers is NP-complete in general.
- 2010-10-08
著者
-
OKAMOTO Yoshio
Graduate School of Infomation Science and Engineering, Tokyo Institute of Technology
-
Otachi Yota
Graduate School Of Information Sciences Tohoku University
-
Okamoto Yoshio
Graduate School Of Information Science And Engineering Tokyo Institute Of Technology
-
UEHARA Ryuhei
School of Information Science, JAIST
-
Uehara Ryuhei
School Of Information Science Jaist
-
Uehara Ryuhei
Jaist Ishikawa Jpn
-
Otachi Yota
Tohoku Univ. Sendai Jpn
-
Otachi Yota
Graduate School Of Information Science Tohoku University
-
UEHARA Ryuhei
School of Information Science
関連論文
- Adaptive Algorithms for Planar Convex Hull Problems
- Bipartite powers of interval bigraphs
- On the geodesic diameter in polygonal domains (コンピュテーション)
- Enumerating All Rooted Trees Including k Leaves
- Efficient Enumeration of All Pseudoline Arrangements
- Spanning tree congestion of k-outerplanar graphs (コンピュテーション)
- Longest Path Problems on Ptolemaic Graphs
- Hardness results and an exact exponential algorithm for the spanning tree congestion problem (コンピュテーション)
- FOREWORD
- Reconstructing sets from distances given by graphs (コンピュテーション)
- Voronoi Game on a Path
- Hardness results and an exact exponential algorithm for the spanning tree congestion problem (コンピュテーション)
- DS-1-11 An Algorithm for Optimally Locating Baselines using Quad Decomposition
- Enumerating All Rooted Trees Including k Leaves
- NP-completeness of generalized Kaboozle
- Reconstruction Algorithms for Permutation Graphs and Distance-Hereditary Graphs
- Computational Complexity of Piano-Hinged Dissections
- Reconstruction Algorithms for Permutation Graphs and Distance-Hereditary Graphs