Skip to content
Open access

Certified Elimination of Source Candidates Under Capacity, Transit-Time, and Deadline Constraints

Sep 2026 · Entropy · Vol 28, pp. 1022 · 0 citations · 37 references
Medicine

TL;DR

An equivalent minimum-cost circulation computation, monotone certificates under parameter uncertainty, and closed-form formulas for bidirected trees, including linear-time evaluation for uniform capacities and an O(|V|log2|V|) centroid decomposition algorithm for heterogeneous capacities are derived.

Abstract

Source identification is constrained not only by network connectivity but also by whether a finite message can reach observed nodes before a deadline. We study deterministic source-candidate elimination in directed networks with arc capacities and transit times. A time-expanded construction gives an exact causal network-coding characterization in which a candidate is retained if and only if its temporal min-cut to every required recipient is at least the message size. Rejection is therefore conservative for any weaker compliant routing or replication protocol. We derive an equivalent minimum-cost circulation computation, monotone certificates under parameter uncertainty, and closed-form formulas for bidirected trees, including linear-time evaluation for uniform capacities and an O(|V|log2|V|) centroid decomposition algorithm for heterogeneous capacities. Protocol-generated experiments show zero true-source eliminations and substantial refinement in routing regimes. Held-out calibration supports transfer to unseen networks. On benchmark representations of 40 real backbone topology families with 50 to 197 nodes, mean candidate retention falls from 99.3% under static screening to 25.3% under exact temporal screening, without true-source elimination. A focused RLNC diagnostic attributes weak refinement in coding-rich regimes to the static screen retaining all candidates and to broad temporal feasibility, while decode-before-forward restrictions create a substantially larger protocol gap.

Read PDF

Similar papers

Preprint Oct 2026

An Efficient Algorithm for the Quickest Path Reliability Problem

This paper proposes an exact algorithm that generates the corresponding lower boundary state vectors without first enumerating minimal paths, and generates the exact complete set of lower bounds without any duplicates.

M. Forghani-elahabad · 0 citations
Preprint Nov 2026

Generalized Flows over Time: Complexity, Structure and Algorithm

It is proved that the generalized maximum flow over time problem remains NP-hard under standard binary encoding, even on lossy two-terminal series-parallel networks, and it is proved that an optimal solution always exists without intermediate storage.

Si-Yuan Chen, Shengminjie Chen, Sui-Xiang Gao et al. · 0 citations
Preprint Oct 2026

Safe Hypergraph Contraction via Capacity-Aware Repair Certificates

Multilevel partitioners shrink circuit hypergraphs through vertex contractions, yet a contraction that satisfies block capacity can still eliminate every optimal balanced bipartition. We develop certified safe coarsening (CSC) to identify contractions that preserve an optimum without computing that optimum. CSC certifi...

Yu-Zhou Deng, Xin-Yi Yang, Ke-Ren Zhu · 1 citation
Preprint Oct 2026

Bidirectionality is Necessary in Cellular Machines for Exact-Arrival Multi-Agent Path Finding

On ranked directed acyclic graphs coupled by vertex conflicts we study exact-arrival multi-agent path finding (departure and arrival pinned in place and time) posed as a distributed output task: every cell must emit its own bit of a valid joint path-support mask. The machines are cellular: one automaton per cell, state...

M. Aono · 0 citations
#edge computing Open access Oct 2026

Maximum Induced Matching: Recursive Computation and an Availability-Uniform Branch-Length Analysis

Induced matchings are a fundamental graph-theoretic concept with applications in secure communication, network flow, and very-large-scale integration. An induced matching in a graph is a set of pairwise non-adjacent edges such that no edge of the graph joins the endpoints of two distinct edges in the set. A maximum ind...

Samer Nofal · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.