84 citations · 228 across the 17 of their papers we have counts for
6 papers · 1 filter
New results for the degree/diameter problem
Michael J. Dinneen, Paul R. Hafner
The results of computer searches for large graphs with given (small) degree and diameter are presented. The new graphs are Cayley graphs of semidirect products of cyclic groups and…
Algebraic constructions of efficient broadcast networks
Michael J. Dinneen, Vance Faber, Michael R. Fellows
Cayley graph techniques are introduced for the problem of constructing networks having the maximum possible number of nodes, among networks that satisfy prescribed bounds on the pa…
VLSI layouts and DNA physical mappings
Michael J. Dinneen
We show that an important problem (-ICG) in computational biology is equivalent to a colored version of a well-known graph layout problem (-CVS).
Obstructions to within a few vertices or edges of acyclic
Kevin Cattell, Michael J. Dinneen, Michael R. Fellows
Finite obstruction sets for lower ideals in the minor order are guaranteed to exist by the Graph Minor Theorem. It has been known for several years that, in principle, obstruction…
The complexity of broadcasting in bounded-degree networks
Michael J. Dinneen
Broadcasting concerns the dissemination of a message originating at one node of a network to all other nodes. This task is accomplished by placing a series of calls over the commun…
A simple linear-time algorithm for finding path-decompositions of small width
Kevin Cattell, Michael J. Dinneen, Michael R. Fellows
We described a simple algorithm running in linear time for each fixed constant , that either establishes that the pathwidth of a graph is greater than , or finds a path-d…