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 Kp,q with ![]() |
|
unit interval graphs, hypercube, generalized hypercube | |
1-SIRS | trees, rings, outerplanars, interval graphs, |
d-dim. tori with the
![]() ![]() |
|
2D-grids with column-wrap-around, graphs with ![]() |
|
chordal ring of degree 4 with chord length ![]() |
|
unit arc-circular graphs, Kp,q with ![]() |
|
2-SLIRS | d-dimensional tori, almost all graphs |
3-SIRS | 2-trees, Petersen graph |
2k+1-SIRS | k-trees |
![]() |
p-plane graphs of genus ![]() |
![]() |
Shuffle-Exchange, Cube Connected Cycles, Butterfly |
![]() |
chordal rings of degree 4 |
![]() |
cubic planar, triangulated planar, series-parallel graphs |
![]() |
graphs of treewidth k,
![]() |
![]() |
Star graph, with
![]() |
![]() |
worst-case graph with m edges,
![]() |
![]() |
worst-case cubic graph |
![]() |
all graphs, with
![]() |