Optimal designs and structured graphs
Title: Optimal designs and structured graphs
DNr: SNIC 2014/1-271
Project Type: SNIC Medium Compute
Principal Investigator: Klas Markström <Klas.Markstrom@math.umu.se>
Affiliation: Umeå universitet
Duration: 2014-10-01 – 2015-10-01
Classification: 10104 10105
Homepage: http://abel.math.umu.se/~klasm/Data/hypergraphs/coveringdesign.html
Keywords:

Abstract

This application concerns time for two subprojects ------------------------------- Structured graphs: One the most important problems in both applications of graph theory and pure graph theory is the design of networks and graph with specified properties. One simple example is to find a network with a given degree and as robust connectivity properties as possible. Another is to find networks on which information can be spread as efficiently s possible.- In this project I and my collaborators are using a computational approach aimed at finding all networks of a given size with given properties. We are both designing efficient algorithms for ouch generations, implementing the algorithms and finally using them to produce complete listings of optimal networks and graphs. We now have the currently most efficient suite of programs for these problems. Our programs have been designed to allow a large program to be broken into non-overlapping subcases which can also be restarted from checkpoint files. The allows us to run our generation procedure as independent serial jobs with short run times. Our current aim is the production of a complete catalogue of graphs with vertex degree 3 without short cycles, and additional properties. These graphs will serve as a testbed for a number of unsolved problems in pure and applied graph theory. ------------------------------- Optimal designs: In a number of problems in both applications and pure combinatorics one is interested in collections of sets with certain extremal properties. One such example is experimental designs where one wishes to minimise the number of trials, another is surveillance where one wishes to monitor an area using the minimum number of sensors, and yet another is in the construction of anonymous signing schemes in cryptography In this project I am using a combination of methods for combinatorial optimisation and combinatorial generation to construct all non-isomorphic sets system which are optimal under certain criteria. In particular I am constructing optimal covering designs and turan hypergraphs. For most cases of the parameters the computations I make both give the first proof of optimally for these designs and the first complete listing of the optimal designs. Part of the work is development of new programs and algorithms for these purposes and part of the work is to actually generate the set systems.