- Title
- Large networks bounded in degree and diameter
- Creator
- Pérez-Rosés, Hebert
- Relation
- University of Newcastle Research Higher Degree Thesis
- Resource Type
- thesis
- Date
- 2012
- Description
- Research Doctorate - Doctor of Philosophy (PhD)
- Description
- In the design of large interconnection networks several (and sometimes conflicting) factors come into play. Two of the most common requirements are: (1) an upper bound on the number of connections attached to each node (the degree of the node in question); and (2) an upper bound on the diameter of the network, which is the distance between the two nodes that are farthest apart. With these two constraints we can try to build a network that is as large as possible, in terms of the number of nodes. In Graph Theory this classic problem is known as the Degree- Diameter Problem, or DDP for short. Research on this problem began in the 60s, but there are fundamental questions that still remain unanswered. There is a well known upper bound (the Moore bound) on the maximum number of nodes that can be achieved, given a maximum degree and a diameter. However, the number of networks reaching the Moore bound (or even approaching it, in the undirected case) is very small. For most combinations of maximum degree and diameter there is a gap (that can be very large for undirected networks) between the largest constructed network and the theoretical upper limit. Consequently, research in this area can be roughly classified into two main categories: (1). Lowering the theoretical upper bound, by proving the nonexistence of networks with a given number of nodes, for a given combination of maximum degree and diameter. (2). Increasing the lower bounds, by constructing ever larger networks, for each combination of maximum degree and diameter. Our research in DDP falls entirely within the second category: we investigate and apply methods to construct large networks. More precisely, we investigate two kinds of methods: (1) Graph compounding, which produces large networks of diameter 6. (2) Algebraic methods, based on Cayley graphs and its generalization, voltage assignment. We have applied algebraic methods to obtain large bipartite networks. Additionally, we introduce a generalization of the Degree-Diameter Problem, which we have called the Degree-Diameter Subgraph Problem, or DDS for short, consisting in finding the largest subnetwork of a given host network, again subject to constraints on the maximum degree and the diameter. It is noteworthy that DDS had not been investigated before, in spite of the fact that it is a natural generalization of DDP, hence we regard this as the main contribution of the thesis. Our research in DDS falls within the two main research directions enumerated above, i.e. lowering the upper bounds, and raising the lower bounds. We have focused on some host networks of practical interest (mainly for parallel computing): the mesh, the hexagonal grid, and the hypercube. For those host networks we have determined Moore-like upper bounds for the largest subnetwork of a given maximum degree and diameter. Then we have applied some ad hoc construction techniques that yield families of subnetworks, which in most cases come quite close to, or even reach the theoretical upper limits. Finally, we discuss DDS from the computational viewpoint. As a combinatorial optimization problem it is NP-hard, hence finding an exact solution for large instances is hopeless with the current state of the art. We propose a heuristic algorithm that approximates the solution in polynomial time, and we investigate its performance, both theoretically and empirically. Our work opens up many new interesting research directions, and we briefly discuss some of them in the thesis.
- Subject
- network design; Degree-Diameter Problem; mesh; hypercube; honeycomb; Degree-Diameter Subgraph Problem; Maximum Degree-and-Diameter Bounded Subgraph
- Identifier
- http://hdl.handle.net/1959.13/933140
- Identifier
- uon:11550
- Rights
- Copyright 2012 Hebert Pérez-Rosés
- Language
- eng
- Full Text
- Hits: 1129
- Visitors: 1663
- Downloads: 301
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT01 | Abstract | 372 KB | Adobe Acrobat PDF | View Details Download | ||
| View Details Download | ATTACHMENT02 | Thesis | 1 MB | Adobe Acrobat PDF | View Details Download |