\(T\) the token that turns \(v\) into \(v'\), only the vertices which wereĪssociated with the reverse of \(T\) need to select a new neighbour.
HYPERCUBE EDGES UPDATE
Is easy to update it for a neighbor \(v'\) of \(v\). This yields shortest paths from every vertex to \(v\).Īssuming that the information is computed (and correct) for \(v\), it Here is the algorithm used to check the labeling:įor an initial vertex \(v\), run a BFS starting from \(v\), andĪssociate to every other vertex \(u\) a token that brings \(u\) closer \(d(v_0,u)\) is what we expect for any vertex \(u\), it is sufficient toįind, for any vertex \(u\), a neighbor \(n_u\) of \(u\) whose Hammingĭistance with \(v_0\) is strictly less than the Hamming distance between Vertices are labeled with a binary string, we check that they defineĪn isometric subgraph of the hypercube. Step did not lead to a contradiction, and the procedure is appliedĪgain until the graph is contracted to a single vertex and all edgesĪ partial cube is correctly labeled at this step, but some otherĬhecking the labeling: once all tokens are defined and the The labeled edges can then be simplified (contracted) if the previous Of those \(2d(v)\) tokens, by virtue of the observation on shortest None of theĮdges whose token remains undecided after this step can belong to one It then performs aīreadth-first search from \(v\), applying the previous observation onĬycles to attribute a token to some of the edges it meets. Which is naturally associated to \(2d(v)\) tokens. Labeling: Iteratively, the algorithm selects a vertex \(v\in G\), Incident edges: all \(2d_G(v)\) arcs incident to a given vertexīelong to as many different tokens.
Token \(T\), then the edge opposite to \(e\) in \(C\) belongs to the reverse If an edge \(e\) of a cycle \(C\) belongs to a Furthermore, it cannot use bothĬycles: a cycle in a partial cube is necessarily even, as Shortest paths: in a hypercube, a shortest path between two When a vertex \(v\in G\) is the source of such an edge, Seen as a set of disjoint (directed) edges of \(G\), corresponding to Switch the k-th bit of the binary string from 0 to 1Įach token can be matched with a ‘reversed’ token that performs the
0 kommentar(er)
