Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
DOI: 10.7155/jgaa.00226 Recognizing Partial Cubes in Quadratic Time David Eppstein Vol. 15, no. 2, pp. 269-293, 2011. Regular paper Abstract We show how to test whether a graph with n vertices and m edges is a partial cube, and if so how to find a distance-preserving embedding of the graph into a hypercube, in the near-optimal time bound O(n2), improving previous O(nm)-time solutions.
|
Published: July 2011. Submitted: February 2011. Final: May 2011. Reviewed: May 2011. Accepted: May 2011. Communicated by Giuseppe Liotta |
Journal of Graph Algorithms and Applications |