On the edge forwarding index problem for small graphs (Q5289367)
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 279415
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On the edge forwarding index problem for small graphs |
scientific article; zbMATH DE number 279415 |
Statements
On the edge forwarding index problem for small graphs (English)
0 references
23 August 1993
0 references
diameter
0 references
routing
0 references
path
0 references
edge forwarding index
0 references
0.9241304397583008
0 references
0.8737905025482178
0 references
0.8614435791969299
0 references
A routing \(R\) of a graph \(G\) of order \(n\) is a set of \(n(n-1)\) paths where each ordered pair of vertices occurs exactly once as terminal vertices of a path. The edge forwarding index \(\pi(\Delta,n)\) is defined as \[ \min\min\max|\{P\in R:e\text{ is on }P\}|, \] where the first minimum is taken over all graphs \(G\) of order \(n\) and maximum degree \(\Delta\), the second over all routings \(R\) of \(G\) and the maximum is taken over all edges \(e\) of \(G\). In the paper \(\pi(\Delta,n)\) is determined for all \(n\leq 15\) and \(\Delta\leq n-1\).
0 references