CS Paper Radar

Computing All-Pairs Shortest Communication Time Paths for Periodically Varying Satellite Networks

Koushik Sinha, Dibakar Saha, Sai Puppala, Bhabani P. Sinha

cs.NI cs.DC ·submitted 2026-10-12 20:29 UTC · v1

Abstract

We address the problem of designing an efficient algorithm for computing the all-pairs shortest-time paths in time-varying networks, specifically targeting the dynamic topological characteristics of low earth orbit (LEO) satellite constellations. We model such temporal graphs as $G = (V, E_t)$, where $V=\{1, 2,\ldots , n\}$ is the set of $n$ vertices in the graph, and $E_t$ is the set of $M$ time-varying edges considered over a total time window of size $T = Mτ$, $τ$ being the duration of each interval in that time window. For such a network, our algorithm finds the all-pair shortest paths in $O(M^2n^3)$-time. A key advantage of our approach is its computational structure, which mirrors two matrix multiplication steps, first in the forward direction and then in the backward direction. This structure of the algorithm makes it exceptionally suitable for parallelization on SIMD architectures like GPUs, thereby offering a significant speedup over traditional shortest-path algorithms and enabling efficient, network-wide message routing in rapidly changing LEO satellite constellations.

Closest papers

Nearest neighbours by meaning across the whole index.

Lightweight Onboard Routing and Topology Co-Construction for Autonomous GNSSs

eess.SY ·2026-09-07 ·Huan Yan, Juan A. Fraire, Rongqin Yang, Wenfeng Li, Kanglian Zhao
similarity 0.63
Abstract · 15 pages, 6 figs

Global navigation satellite systems (GNSSs) can already plan their inter-satellite link (ISL) topology onboard, leaving routing as the last step toward autonomous networking. In GNSS ISLs, each satellite links to at most one peer per time slot. We exploit this structure to replace end-to-end path search with a single backward sweep over the slots. The proposed method, DS-SMFP, propagates earliest-arrival times backward from each destination and outputs a STORE/FORWARD decision for every slot, satellite, and destination, in time linear in the number of slots and with working memory independent of the planning horizon. Because each slot needs only its own topology and the delivery state of the next one, routing can steer link selection while the topology is built. This slotwise dependency enables Master-Oriented Topology--Routing Co-Construction (MTRCC), which favors traffic to and from a master satellite performing onboard orbit determination. In a 24-h, 30-satellite BeiDou scenario, DS-SMFP matches the delays of Contact Graph Routing (CGR) and shortest path tree (SPT) routing while running over 180 times faster and using over 36 times less peak routing working memory. Compared with fair contact plan (FCP) topology, MTRCC reduces mean master-related traffic delays by over 10\%, with an approximately 3\% increase in mean PDOP. This paper provides a methodological foundation for efficient autonomous GNSS networking.

0.27

Parallel Algorithms for Higher-Order Temporal H-Index Computation

cs.DS ·2026-11-06 ·Lutz Oettershagen
similarity 0.58
Abstract

Ranking vertices by importance is a fundamental task in network mining. The H-index provides such a ranking by asking how many neighbors are themselves well connected; its higher-order temporal variant recursively applies this idea over time-respecting neighborhoods in temporal networks. Scaling its computation is difficult because the existing streaming algorithm intertwines temporal processing with H-index order, incurring maximum-degree-dependent costs and exposing little parallelism. We show that the temporal dependencies can instead be resolved once: each edge's time-dependent lookup is mapped to a fixed successor position, turning every H-index order into a parallel gather followed by a segmented suffix-H computation. Based on this reformulation, we derive a linear-work suffix-H algorithm, a parallel multicore CPU implementation, degree-adaptive GPU kernels, and a multi-GPU scheme that exchanges only distinct remotely queried states. Experiments on synthetic and real-world temporal graphs show that the reformulation alone is substantially faster than the streaming algorithm, and that GPUs add order-round speedups exceeding an order of magnitude over our multicore implementation on synthetic inputs with up to one billion temporal edges. On a 636M-edge Reddit network, eight GPUs compute 128 orders in 3.6 s of round time, whereas the streaming algorithm does not finish within an hour even at order 8.

0.30

On the Lack of Periodicity of Walker Satellite Constellation Routing Tables

cs.IT cs.NImath.DS ·2026-09-29 ·Chang-Sik Choi, François Baccelli
similarity 0.57
Abstract · submitted to IEEE Journal

In a referential that rotates with Earth, the dynamics of the configurations of satellites in a Delta Walker constellation can be analyzed as a dynamical system as a function of a translation on the torus. This paper extends this type of analysis to routing over a Walker constellation, leveraging fixed ground relays. It considers any deterministic, time-invariant routing rule on such a collection of satellites and relays. The main object of interest is the routing table associated with this rule, which specifies, for all source-destination pairs, a route made of satellites and relays between them, for instance the shortest, together with angular information on next hop at each step of the route, which is essential for beamforming in this context. The main result is that, for each such routing rule, the routing table inherits the dichotomy of the torus flow: when the ratio of the Earth-spin and satellite angular speeds is rational, the routing table process is periodic with the same period as the constellation. When it is irrational, the table is non periodic but admits ergodic long-run averages which can be computed as ensemble averages w.r.t. an explicit invariant measure. Simulations with mixed satellite--gateway greedy routing illustrate these findings in terms of both temporal and spectral properties of the Walker routing table time series. The paper also discusses how to define metrics that cope with such non periodic fluctuations when present. This is illustrated by a comparison of the round-trip times between two far away cities as offered by a Walker constellation using greedy routing on one side, and by the currently available terrestrial fiber on the other side. It is shown how ergodicity can be used to make this comparison between the time varying instantaneous round trip times of the constellation and the constant round trip time of the fiber network meaningful.

0.28

Time-Optimal APSP and Matrix Multiplication in Classes of Linear Neighborhood Complexity

cs.DS cs.CCcs.DMmath.CO ·2026-08-25 ·Édouard Bonnet, Julien Duron, Marcin Pilipczuk, Marek Sokołowski, Szymon Toruńczyk
similarity 0.56
Abstract · 31 pages, 5 figures

The notion of linear neighborhood complexity is a very general structural assumption on a graph class, covering most classes of sparse graphs such as planar graphs, graphs excluding a fixed (topological) minor, or bounded expansion graphs, as well as many structured classes of dense graphs, such as graphs of bounded clique-width, twin-width, merge-width, or flip-width. In this work, we present $O(n^2)$-time optimal algorithms for $n$-vertex graphs coming from a class of linear neighborhood complexity for the following problems: $\bullet$ All-Pairs Shortest Paths, $\bullet$ the multiplication of the adjacency matrix $M$ of the input graph with any $n \times n$ matrix. More specifically, after a quadratic preprocessing, we can multiply $M$ with any $n$-vector in $O(n)$ time. This solves several questions raised in [Bonnet, Kim, Geniet, Moon; ICALP '26], and improves and generalizes results in several other recent papers [Bonnet, Giocanti, Ossona de Mendez, Thomassé; STACS '23], [Bannach, Marwitz, Tantau; STACS '24], [Anand, van den Brand, McCarty; NeurIPS '26], [Kozma, Opler '26], and [Cardinal, McCarty, Yuditsky '26]. We also extend our results to classes of bounded VC density. In classes of linear neighborhood complexity, we also give a triangle-detection algorithm in randomized linear time $O(n+m)$ in $n$-vertex $m$-edge graphs, a $K_4$-detection algorithm in randomized $O(n \log^5 n + m \log n)$ or deterministic $O(n^2)$ time, and a $K_5$-detection algorithm in randomized $O(n \log^9 n + m \log^5 n)$ time.

0.37

Resource Slicing for Time-Sensitive Data Traffic in Non-Terrestrial Networks with FSO ISLs

eess.SP ·2026-10-22 ·Abid Afridi, Alexis A. Dowhuszko, Risto Wichman, Jyri Hämäläinen
published similarity 0.55
Abstract · 6 pages, 7 figures, 1 table. Accepted for presentation at IEEE GLOBECOM 2026 Workshops

In multi-hop Low Earth Orbit (LEO) satellite networks, time-sensitive packets experience queueing across multiple satellite hops, causing per-hop waiting times that accumulate and make the maximum end-to-end (E2E) delay difficult to guarantee. This paper presents a novel multi-hop slicing framework that reserves time-frequency resources for each time-sensitive flow of data originating at each satellite, aiming to maintain the reservation of communication resources along every inter-satellite link (ISL) on its route to the ground station (GS). The number of time-frequency resource blocks (RBs) reserved per-hop is determined from the data packet arrival statistics, E2E delay budget, and target level of reliability. Reservations on consecutive links are temporally aligned to enable pipelined forwarding of the time-sensitive data flows aggregated from terrestrial user terminals on the different LEO satellites. We evaluate the proposed framework against conventional scheduling and resource-allocation baselines, including pure time-division multiple access (Pure-TDMA), first-in-first-out (FIFO), and farthest-satellite-first (FSF), over the same multi-hop LEO satellite path. Under light traffic conditions, the baseline schemes provide comparable delay performance; however, their high-percentile delays increase sharply as data traffic load grows, whereas the proposed framework exhibits substantially slower delay growth. At the high arrival rate and high reliability target considered, the proposed scheme requires about 31 ms, a factor of 2.5-6.8 lower than the 76, 180, and 210 ms required by FIFO, FSF, and Pure-TDMA.

0.43

The Complexity of Traffic Engineering in Segment Routing Networks

cs.DS ·2026-11-13 ·Matthias Bentert, Stefan Schmid
theory similarity 0.55
Abstract

Segment routing is a modern variant of source routing which has recently become popular in the Internet. It allows operators to equip network packets with an additional header which specifies segments: a list of waypoints the packet needs to traverse on its way to the destination. This is reminiscent of Valiant routing in parallel computing and introduces an additional degree of freedom in traffic engineering. This flexibility can be exploited to minimize congestion in the network. This paper sheds light on the computational complexity of traffic engineering in segment routing networks. We consider two problem variants: a fixed-length variant where link weights are given and only waypoints can be chosen, and a variable-length variant where additionally the network operator can also choose the link weights, which then define the shortest paths taken between the waypoints. We prove that the first variant is NP-hard even if the network graph is planar and if all demands and link weights are 1. We also show that the second variant is NP-hard already for planar network graphs with all demands being 1. On the positive side, we present a compact and general mixed integer linear program to compute exact solutions for the first variant.

0.32

Space-Efficient Hierholzer for Undirected Graphs

cs.DS cs.DM ·2026-08-19 ·Elena Grigorescu, Ziad Ismaili Alaoui, Tamio-Vesa Nakajima, Shayan Shirazi Mofrad, Sebastian Wild
similarity 0.55
Abstract

We present a simple linear-time algorithm that outputs an Eulerian tour of an undirected multigraph with $n$ vertices and $m$ edges, if one exists, in $O(m)$ time and using $O(n)$ words of working memory. The input is given as read-only adjacency lists, and the output is written to an append-only stream in traversal order. Our algorithm first finds a sparse spanning circuit (a skeleton), then traverses the circuit step-by-step, repeatedly outputting further circuits rooted at the current vertex. This solves a problem left open by Ismaili Alaoui, Plump, and Wild (SOSA 2026): their space-efficient variant of Hierholzer's algorithm handles general directed multigraphs, but it is unclear how to generalize it to general undirected multigraphs. Our result completes the picture in the read-only model for space-efficient output of Eulerian tours.

0.47

A simple algorithm for computing Hamilton paths on independent set polytopes

cs.DM math.CO ·2026-09-07 ·Jean Cardinal, Pia Herkenrath, Torsten Mütze, Francesco Verciani
similarity 0.55
Abstract

The independent set polytope, or stable set polytope, of a graph $G$ is the 0/1-polytope defined by the convex hull of the characteristic vectors of all independent sets of $G$. We present a simple algorithm for computing a Hamilton path on the independent set polytope of a given $n$-vertex graph $G$ with amortized delay $\mathcal{O}(n)$. The independent sets are listed such that two consecutive sets differ either in removing a vertex, or adding a vertex and removing its neighbors from the independent set, i.e., the symmetric difference between two consecutive independent sets induces a star in $G$. As applications of this result, we obtain an algorithm to compute a Hamilton path on the matching polytope of an $m$-edge graph $G$ with worst-case delay $\mathcal{O}(m)$, which lists all matchings of $G$ in such a way that the symmetric difference between two consecutive matchings is a path on at most three edges. Furthermore, we obtain an algorithm to compute a Hamilton path on the chain polytope and order polytope of an $n$-element poset $P$ with amortized delay $\mathcal{O}(n)$, which lists all antichains of $P$ or all ideals of $P$, respectively, by star exchanges. Our algorithms are derived from the generic framework proposed by Merino and Mütze (FOCS'23+SICOMP'24) for computing Hamilton paths on arbitrary 0/1-polytopes, which uses a linear optimization procedure as a black box. Our algorithms bypass solving the computationally intractable maximum weight independent set problem by a simple and purely combinatorial greedy rule.

0.25