In the following table, only shortest paths IRS are considered, and n denotes the number of nodes of the graph.
IRS classes | Graphs |
1-SLIRS | paths, complete graphs, d-dimensional grids, |
d-dimensional tori with each dimension of length , | |
complete bipartite graphs K_{p,q} with , | |
unit interval graphs, hypercube, generalized hypercube | |
1-SIRS | trees, rings, outerplanars, interval graphs, |
d-dim. tori with the largest dim. of length , | |
2D-grids with column-wrap-around, graphs with , | |
chordal ring of degree 4 with chord length , | |
unit arc-circular graphs, K_{p,q} with | |
2-SLIRS | d-dimensional tori, almost all graphs |
3-SIRS | 2-trees, Petersen graph |
2^{k+1}-SIRS | k-trees |
-SIRS | p-plane graphs of genus |
-IRS | Shuffle-Exchange, Cube Connected Cycles, Butterfly |
-SIRS | chordal rings of degree 4 |
-IRS | cubic planar, triangulated planar, series-parallel graphs |
-IRS | graphs of treewidth k, |
-IRS | Star graph, with |
-IRS | worst-case graph with m edges, |
-IRS | worst-case cubic graph |
-SLIRS | all graphs, with |