This work considers the problem of finding, for a given degree sequence, the network structure displaying the smallest possible average shortest-path length and proposes a fast algorithm to construct approximate solutions to such a degree-constrained distance-minimization problem.
Abstract
Designing networks that minimize distances and satisfy structural constraints is a fundamental task across transportation, communication, and biological systems. Here, we consider the problem of finding, for a given degree sequence, the network structure displaying the smallest possible average shortest-path length. While exact solutions are available in linear time for trees, such an optimization problem becomes computationally infeasible as soon as loops are allowed in the networks. We propose a fast algorithm to construct approximate solutions to such a degree-constrained distance-minimization problem. Accordingly, edges are first created between high-degree nodes; then, additional connections are placed following the rules of the standard configuration model. In spite of its simplicity, the algorithm displays outstanding performance as demonstrated in our systematic experiments on both synthetic and real degree sequences. Our method is particularly effective on synthetic degree sequences displaying medium levels of heterogeneity. When applied to degree sequences of real networks, the proposed algorithm is able to reduce the all-pair shortest path of real structures by 20%, on average. We perform a validation on small-sized networks, where we compare the shortest-path distance of the networks generated with our algorithm against those obtained via simulated annealing optimization. Although simulated annealing yields slightly better structures, our proposed algorithm provides nearly identical solutions at a substantially lower computational cost, making it a solid method in applications concerning large-scale systems.
Centroids are used to compute an arbitrary number of simple paths with some important benefits: the expansion of a single centroid delivers an arbitrary number of paths; only a single Dijk-stra search is required to complete the task; the same algorithm can be easily coupled with heuristics that improve search efficiency.
The Single Source Shortest Path (SSSP) problem focuses on finding the shortest paths from a source vertex to all other vertices in a graph. This problem is crucial in various domains, including transportation, telecommunications and urban planning. Although Dijkstra's algorithm is effective for solving the SSSP in general cases, in some special cases, such as two-dimensional mesh networks (2DMN), its performance is not satisfactory. To address this limitation, this paper presents an improved approach, i.e., the row-by-row dynamic programming (RRDP) algorithm, which is specifically optimized for 2DMNs and can significantly reduce computation times, although in worst case the complexity of RRDP is higher than Dijkstra's algorithm. We tested the RRDP algorithm against the traditional Dijkstra's algorithm using the same 2DMN instances, and found that RRDP runs much faster than Dijkstra's algorithm on most instances. This innovation offers new insights and practical solutions for improving path planning algorithms in grid network environments.
S. Sun, Yuwei Sang, Zhang-Hua Fu· 2026 6th International Confe...· 0 citations
In graph theory and its applications to networking, such as telecommunications or transportation, path-finding is a central problem. While single-path algorithms are well established, methods for handling sets of multiple paths are less developed. A companion paper introduced a formal model for defining attributes over sets of paths based on their structural properties; this paper addresses that model's practical implementation. We present an optimized algorithm for computing cut sets of a path set—a nontrivial task that can be infeasible without efficient methods—and validate its performance via systematic benchmarks on network simulations of varying complexity. Additionally, we introduce a vectorized computational framework that expresses property calculations as matrix operations, enabling concise implementations in array-oriented languages. Together, these contributions establish practical foundations for the companion model, demonstrating that its implementation is both feasible and characterized by predictable, acceptable execution times.
G. Fiaschi, Carlo Vitucci, Thomas Westerbäck et al.· International Conference on...· 0 citations
It is proved that the problem of defining a bounded cost set of nodes S such that the influence spreading from S in G, within a given time bound, is as large as possible, and that the problem is NP-hard, even in simple networks like complete graphs and trees.
F. Cicalese, G. Cordasco, L. Gargano et al.· 0 citations
We study the shortest-path problem on graphs with positive real-valued edge weights. Given a source vertex $s$ and a target vertex $t$, the goal is to calculate the length of the shortest path from $s$ to $t$. We are particularly interested in instances that can be solved in sublinear time. Recently, Haeupler, Hlad\'ik, Rozho\v{n}, Tarjan, and T\v{e}tek proved that (a version of) the bidirectional Dijkstra's algorithm is instance-optimal on positively weighted multigraphs, both directed and undirected, considering the number of vertices and edges queried by the algorithm. However, multigraphs are not the canonical setting for the shortest-path problem. The problem is typically formulated on simple graphs without loops and parallel edges. They therefore left as an open problem whether bidirectional Dijkstra remains instance-optimal on simple weighted graphs. We answer this question, but for simple graphs, the answer is more complex, depending on the setting. We show that bidirectional Dijkstra is still instance-optimal on simple undirected weighted graphs under the order-oblivious model, where incident edges are given in a random order. In contrast, under the order-dependent model, where incident edges have a given order, we show that bidirectional Dijkstra is not instance-optimal. For simple directed weighted graphs, we show that bidirectional Dijkstra is not instance-optimal under either the order-oblivious or the order-dependent model, being off by a factor of $\Theta(m/n)$ in both cases. We further show that no algorithm can have instance-optimality ratio $o(m/n)$ under the order-dependent model, or under the order-oblivious model when $m=O(n\sqrt{n})$. On the positive side, the above results imply that bidirectional Dijkstra is instance-optimal up to logarithmic factors on all sparse directed and undirected graphs satisfying $m/n=\log^{O(1)} n$.
Christian Bertram, Mads Vestergaard Jensen, Mikkel Thorup et al.· 0 citations
The results support HON as a simple low-degree construction for structured inter-group communication, whereas higher-radix, adaptive, or more richly connected fabrics remain better suited to less structured traffic and larger bandwidth demand.
Han Ni Soe, Yao Zhang, Zhipeng Xu· Parallel Processing Letters· 0 citations