An efficient shortest path routing on the hypercube with blocking/faulty nodes
Bibliographic record
Abstract
Summary We investigate fault‐tolerant shortest path problem in the hypercube between two nodes where some nodes are faulty (or blocked) and thus cannot be used in routing. Previously, several similar problems were studied where proposed algorithms are distributed and local‐information‐based, that is, each node in the network knows only its neighbor's status (faulty or not) and they also look for optimal or near‐optimal paths. There have been studies that established some sufficient conditions for these paths to exist. Since these conditions are only sufficient, there could be shortest paths that will be missed by these conditions. We study the problem under the assumption that for two given nodes, a source node s , a target node t , only s requires to have a global information of the network in order to find a shortest path to t , should it exist. A shortest path is defined as the Hamming distance between s and t . This problem can be solved by trivial algorithms. The first is to try all possible paths. In an n ‐dimensional hypercube with 2 n vertices, this method would cost at least n! time. Another method is to perform a standard shortest path finding algorithm, which would require at least 2 n time. A routing algorithm has been previously developed which is efficient in certain situations. However, in the worst case, its running time could be exponential in the hypercube dimension. We propose an efficient algorithm with running time of O ( n 3 m 2 ) , polynomial in n , the hypercube dimension, and m , number of blocking nodes. We gain our efficiency by reducing the routing problem to a permutation problem which can be solved using inclusion‐exclusion principle. We finally use dynamic programming technique to optimally count the terms. With the proposed algorithm, not only can we find a shortest path, if such a path does exist, but we can also count all possible shortest paths.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
How this classification was reachedexpand
Full frame distilled prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. Learned from the 10,348 direct Codex labels and 10,348 direct Gemma labels. Candidate is the union of thresholded teacher heads; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels or direct frontier model labels.
Codex and Gemma teacher scores by category
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.000 | 0.000 |
| Meta-epidemiology (narrow) | 0.000 | 0.000 |
| Meta-epidemiology (broad) | 0.000 | 0.000 |
| Bibliometrics | 0.000 | 0.000 |
| Science and technology studies | 0.000 | 0.000 |
| Scholarly communication | 0.000 | 0.001 |
| Open science | 0.000 | 0.000 |
| Research integrity | 0.000 | 0.000 |
| Insufficient payload (model declined to judge) | 0.000 | 0.000 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from itClassification
machine, unvalidatedMachine predicted; a candidate call from one teacher head, not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".