On Recursively Directed Hypercubes

  • Carmel Domshlak

Abstract

In this paper we introduce the recursively directed hypercubes, and analyze some of their structural properties. We show that every recursively directed hypercube is acyclic, and has a unique pair of source and sink nodes. The main contribution of the paper is an analysis of distances between the nodes in such a graph. We show that the distance from the source node to any other node, and from any node to the sink node is bounded by $n+1$, where $n$ is the dimension of the hypercube, but the diameter of a recursively directed hypercube may be exponential in $n$.

Published
2001-05-07
Article Number
R23