| HAL-Inria | Publications, software ... of Inria's scientists |
Journal articles
On bipartite powers of bigraphs
Abstract : 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.
Cited literature [19 references]
https://hal.inria.fr/hal-00990585
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Tuesday, May 13, 2014 - 4:27:33 PM
Last modification on : Thursday, September 7, 2017 - 1:03:39 AM
Long-term archiving on: : Monday, April 10, 2017 - 10:38:09 PM
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Tuesday, May 13, 2014 - 4:27:33 PM
Last modification on : Thursday, September 7, 2017 - 1:03:39 AM
Long-term archiving on: : Monday, April 10, 2017 - 10:38:09 PM
File
2132-7332-1-PB.pdf
Files produced by the author(s)