Jul 2026· IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences· 0 citations· 9 references
Computer Science
TL;DR
This paper studies local failover schemes that minimize the number of rewritable bits in the packet header on directed graphs with $k-arc failures and shows that their scheme is nearly optimal when the number of faulty arcs is approximately less than the number of nodes.
Abstract
The local failover routing is a mechanism that routes a packet from a source to a destination only using pre-calculated routing tables, even when several edges fail. In this paper, we study local failover schemes that minimize the number of rewritable bits in the packet header on directed graphs with $k$-arc failures. There are many studies of failover routing on undirected graphs, and it has been investigated whether routing is possible depending on the number of bits in the packet header, the type of failure, the graph properties, etc. In contrast, there is not much research on directed graphs. Van et al.~first showed the upper and lower bounds of rewritable bits in the packet header on directed graphs. However, their results showed a large gap between the upper and lower bounds. The main contribution of this paper is to close the gap between the upper and lower bounds. Specifically, we show that our scheme can route packets with $k$ faulty arcs if the packet header has $\min(k \log ( \frac{e(2n+k-3)}{k}, 2n \log ( \frac{e(2n+k-3)}{2n})))$ rewritable bits, where $n$ is the number of nodes. Moreover, any local failover routing scheme needs $\Omega(k\lceil\log\frac{n}{k}\rceil)$ rewritable bits when the number of faulty arcs is equal to or less than $\frac{3(n-1)}{8}$ and $\frac{n-1}{4}$ rewritable bits when the number of faulty arc is more than $\frac{3(n-1)}{8}$. This result means our scheme is nearly optimal when the number of faulty arcs is approximately less than the number of nodes.
This paper presents detailed algorithm for calculating L-LSR coefficient, and shows that L-LSR algorithm not only performs better than OSPF, but also has verySignificant performance improvement over the other LSR family of algorithms.
This paper identifies an algebraic property of cycles, which is called centripetalism, that characterizes the existence of unique stable routings for all possible destinations in a network and failure scenarios and presents the Consistent-Tree algorithm, which either produces a stable routing or reports the presence of a non-centripetal cycle.
Ricardo Santos, J. L. Sobrinho· Proceedings of the ACM SIGCO...· 0 citations
ABSTRACT We address the Positive Influence Dominating Set problem (PIDS), which involves identifying the smallest group of vertices in a given network that maximizes influence throughout the network. Formally, given a graph G = (V, E), representing the network, we look for a subset of vertices P ⊆ V such that each vertex v i ∈ V \ P has at least ρ deg G (v i ) neighbors in P, where deg G (v i ) is the degree of v i , and 0 < ρ < 1. The problem is known to be NP-hard in general graphs and remains NP-hard even when restricted to certain particular classes, such as chordal graphs. In this paper, we develop an exact algorithm based on the Branch and Bound approach for solving PIDS on chordal graphs. The effectiveness of the proposed algorithm is demonstrated through numerical experiments conducted on various randomly generated chordal graphs.
Y A Bekhti, M. Lalou, Méziane Aïder et al.· Pesquisa Operacional· 0 citations
Simulation results showed that, for all traffic profiles, the new routing algorithms designed for the topologies of circulant networks with rectangular L-shapes outperform other algorithms with similar metrics in terms of memory consumption.
M. Malikov, E. Monakhova, E. R. Rzaev et al.· Uchenye Zapiski Kazanskogo U...· 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
A new proof that the multiple-unicast conjecture holds for networks with at most six coding nodes, without computer-aided search, is given, and it is shown that if the conjecture holds on $\Gamma_{3,3}$, then it holds whenever no three sessions have six distinct terminal locations.
Sirui Liu, Linfeng Que, Zongpeng Li et al.· 0 citations