Open AccessRandom Graphs and Algorithms
Author(s) -
Tony Johansson
Publication year - 2017
Publication title -
kilthub repository
Language(s) - English
DOI - 10.1184/r1/6721244
Subject(s) - random graph , combinatorics , theme (computing) , mathematics , chordal graph , indifference graph , bounded function , random function , discrete mathematics , computer science , random variable , graph , statistics , operating system , mathematical analysis
This thesis is concerned with the study of random graphs and random algorithms. There are three overarching themes. One theme is sparse random graphs, i.e. random graphs in which the average degree is bounded with high probability. A second theme is that of finding spanning subsets such as spanning trees, perfect matchings and Hamilton cycles. A third theme is solving optimization problems on graphs with random edge costs.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom