next up previous contents
Next: Variations on the Interval Up: Specific Class of Graphs Previous: Graph Operators   Contents


Summary

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 $\leqs 4$,
  complete bipartite graphs Kp,q with $p,q \geqs 2$,
  unit interval graphs, hypercube, generalized hypercube
1-SIRS trees, rings, outerplanars, interval graphs,
  d-dim. tori with the $2^{\mbox{\small nd}}$ largest dim. of length $\leqs 4$,
  2D-grids with column-wrap-around, graphs with $n \leqs 6$,
  chordal ring of degree 4 with chord length $\leqs 3$,
  unit arc-circular graphs, Kp,q with $p,q \geqs 1$
2-SLIRS d-dimensional tori, almost all graphs
3-SIRS 2-trees, Petersen graph
2k+1-SIRS k-trees
$\floor{3p/2+\gamma}$-SIRS p-plane graphs of genus $\gamma$
$\Omega(n^{1/2-\varepsilon})$-IRS Shuffle-Exchange, Cube Connected Cycles, Butterfly
$\floor{2\sqrt{n}}$-SIRS chordal rings of degree 4
$\Omega(\sqrt{n})$-IRS cubic planar, triangulated planar, series-parallel graphs
$\Omega(\sqrt{kn})$-IRS graphs of treewidth k, $2 \leqs k \leqs (n/3)^{1/3}$
$\Omega(f(n))$-IRS Star graph, with $f(n) = n((\log\log{n})/\log{n})^5$
$\Omega(m\!-\!n)$-IRS worst-case graph with m edges, $n \leqs m \leqs 3n/2$
$\Omega(n)$-IRS worst-case cubic graph
$\alpha(n)$-SLIRS all graphs, with $\alpha(n) < n/4 + (1/4)\sqrt{2n\ln{(3n^2)}}$


next up previous contents
Next: Variations on the Interval Up: Specific Class of Graphs Previous: Graph Operators   Contents

2000-03-21