Home Issues About JGAA Instructions for Authors
 
DOI: 10.7155/jgaa.00226
Recognizing Partial Cubes in Quadratic Time
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.
Submitted: February 2011.
Reviewed: May 2011.
Accepted: May 2011.
Final: May 2011.
Published: July 2011.
Communicated by Giuseppe Liotta
article (PDF)
BibTeX