Recognizing Partial Cubes in Quadratic Time

Authors

  • David Eppstein

DOI:

https://doi.org/10.7155/jgaa.00226

Keywords:

partial cube , isometric embedding , hypercube , distance labeling

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.

Downloads

Download data is not yet available.

Downloads

Published

2011-02-01

How to Cite

Eppstein, D. (2011). Recognizing Partial Cubes in Quadratic Time. Journal of Graph Algorithms and Applications, 15(2), 269–293. https://doi.org/10.7155/jgaa.00226

Issue

Section

Articles

Categories