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.
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.
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
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...
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...
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· AppliedMath· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.