| Presentation | 2010-10-15 Bipartite powers of interval bigraphs Yoshio OKAMOTO, Yota OTACHI, Ryuhei UEHARA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Bipartite power / Interval bigraph / Bipartite permutation graph / NP-completeness |
| Paper # | COMP2010-36 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2010/10/8(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Bipartite powers of interval bigraphs |
| Sub Title (in English) | |
| Keyword(1) | Bipartite power |
| Keyword(2) | Interval bigraph |
| Keyword(3) | Bipartite permutation graph |
| Keyword(4) | NP-completeness |
| 1st Author's Name | Yoshio OKAMOTO |
| 1st Author's Affiliation | Graduate School of Information Science and Engineering, Tokyo Institute of Technology() |
| 2nd Author's Name | Yota OTACHI |
| 2nd Author's Affiliation | Graduate School of Information Sciences, Tohoku University |
| 3rd Author's Name | Ryuhei UEHARA |
| 3rd Author's Affiliation | School of Information Science, JAIST |
| Date | 2010-10-15 |
| Paper # | COMP2010-36 |
| Volume (vol) | vol.110 |
| Number (no) | 232 |
| Page | pp.pp.- |
| #Pages | 5 |
| Date of Issue | |