Complexity of the Forwarding Index Problem (Q3136613)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 425595
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Complexity of the Forwarding Index Problem |
scientific article; zbMATH DE number 425595 |
Statements
Complexity of the Forwarding Index Problem (English)
0 references
14 October 1993
0 references
NP-completeness
0 references
routing
0 references
network
0 references
forwarding index
0 references
0.8763664364814758
0 references
0.8607574701309204
0 references
0.8555759191513062
0 references
0.8528178930282593
0 references
0.8405290842056274
0 references
The forwarding index problem is, for a given connected graph \(G\) and an integer \(k\), to find a way of connecting each ordered pair of vertices by a path so that every vertex is an internal point of at most \(k\) such paths. Such a problem arises in the implementation of algorithms on a distributed architecture, a model of distributed computation being represented by network of processors treating and forwarding synchronous messages and a physical constraint on the number of messages that can be treated by a single processor. More formally, a routing \(R\) of a graph \(G\) of order \(n\) is a set of \(n(n-1)\) elementary paths specified for all ordered pairs of vertices of \(G\). The load of a vertex \(v\) by \(R\) denoted by \(\xi(G,R,v)\) is the number of paths \(p\) of \(R\) passing through \(v\) such that \(v\) is not an end vertex of \(p\). The forwarding index \(\xi(G,R)\) of a network \((G,R)\) is the maximum load of a vertex by \(R\), i.e. \(\xi(G,R)=\max_{v \in V(G)} \xi(G,R,v)\). Now, the forwarding index of \(G\) is the minimum forwarding index of a network \((G,R)\), that is, \(\xi(G)=\min_ R\xi(G,R)\). It is proved that the forwarding index problem is NP-complete even if the diameter of the graph is 2, thereby answering a question of \textit{F. Chung}, \textit{E. Coffman}, \textit{M. Reiman} and \textit{B. Simon} [IEEE Trans. Inform. Theory, 33, 224-232 (1987; Zbl 0626.94019)] concerning the complexity of the problem.
0 references