“A fast algorithm for finding dominators in a flowgraph is presented. The algorithm uses depth-first search and an efficient method of computing functions defined on paths in trees.” The Lengauer–Tarjan algorithm #paper from 01979. #toread #compilers #graphs #algorithms “A vertex v dominates another vertex w≠v in G if every path from [the start vertex] r to w contains v.”
on 02024-12-12Hmm, in shuffle-exchange #graphs, each node can transmit to the node whose ID number has the lowest bit flipped, or the node whose ID number is rotated one bit to the left from its own. So each node has degree 3 (or directed degree 2), which is the smallest node degree a nontrivial network can have, but the longest path length (diameter?) in a shuffle-exchange graph of 2^N nodes is only 2N, because the path from node 1111...111 to 0000...000 involves N rotation links and N bit-flipping links. Tomas Lang and Harold Stone, 01976. Relevant to #HPC #topomania, because its diameter is worse than a hypercube’s only by a factor of 2, but has only 2 outgoing links per node instead of N.
on 02023-10-21