skill@prg.oxford.ac.uk (02/04/89)
There is indeed a vast literature on static interconnection networks
with particular degree. The network you choose for a particular
configuration depends heavily on other concerns such as fault tolerance,
known routing properties, absence of hot spots and so on. I've
included a few references at the end -- if you really want more, I
have several hundred on-line in BiBTeX format.
The problem of determining the largest network of given valence and
diameter is also a long-standing one. A theoretical upper bound on
the size of a network is known (see papers with (d,k) in the title
below). It is known that only four sets of parameters correspond
to graphs attaining this bound, and in that sense the problem is
solved. However, it's a fascinating problem because the largest known
examples of graphs for particular valence and diameter are usually
orders of magnitude smaller than the upper bound would suggest is possible.
And in many cases the largest graphs have been generated randomly.
This suggests that there is a deep reason which, if understood, would
produce a much smaller upper bound; but some good people have tried
without success. However, if you're looking for a Ph.D subject....
-David Skillicorn
skill@uk.ac.oxford.prg
References:
@ARTICLE{,
AUTHOR = {C. Delorme and G. Farhi},
TITLE = {Large Graphs with Given Degree and Diameter --- Part
{I}},
JOURNAL = {IEEE Transactions on Computers},
VOLUME = {C-33, No.9},
PAGES = {857--859},
YEAR = {1984},
MONTH = {September},
}
@ARTICLE{,
AUTHOR = {K.W. Dhoty},
TITLE = {New Designs for Dense Processor Interconnection
Networks},
JOURNAL = {IEEE Transactions on Computers},
PAGES = {447--450},
YEAR = {1984},
MONTH = {May},
}
@ARTICLE{,
AUTHOR = {T.Y. Feng},
TITLE = {A Survey of Interconnection Networks},
JOURNAL = {Computer},
PAGES = {12--27},
YEAR = {1981},
MONTH = {December},
}
@ARTICLE{,
AUTHOR = {M.R. Jerrum and S. Skyum},
TITLE = {Families of Fixed Degree Graphs for Processor
Interconnection},
JOURNAL = {IEEE Transactions on Computers},
VOLUME = {C-33, No.2},
PAGES = {190--194},
KEYWORDS = {moore graphs de bruijn graphs},
YEAR = {1984},
MONTH = {February},
}
@ARTICLE{,
AUTHOR = {G. Memmi and Y. Raillard},
TITLE = {Some New Results about the (d,k) Graph Problem},
JOURNAL = {IEEE Transactions on Computers},
VOLUME = {C-31, No.8},
PAGES = {784--791},
KEYWORDS = {graphs},
YEAR = {1982},
MONTH = {August},
}