Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Randomised techniques in combinatorial algorithmics

Tools
- Tools
+ Tools

Zito, M. (1999) Randomised techniques in combinatorial algorithmics. PhD thesis, University of Warwick.

[img]
Preview
PDF
WRAP_THESIS_Zito_1999.pdf - Submitted Version - Requires a PDF viewer.

Download (1112Kb) | Preview
Official URL: http://webcat.warwick.ac.uk/record=b1370634~S1

Request Changes to record.

Abstract

Probabilistic techniques are becoming more and more important in Computer Science. Some of them are useful for the analysis of algorithms. The aim of this thesis is to describe and develop applications of these techniques. We first look at the problem of generating a graph uniformly at random from the set of all unlabelled graphs with n vertices, by means of efficient parallel algorithms. Our model of parallel computation is the well-known parallel random access machine (PRAM). The algorithms presented here are among the first parallel algorithms for random generation of combinatorial structures. We present two different parallel algorithms for the uniform generation of unlabelled graphs. The algorithms run in O(log<sup>2</sup> n) time with high probability on an EREW PRAM using O(n<sup>2</sup>) processors. Combinatorial and algorithmic notions of approximation are another important thread in this thesis. We look at possible ways of approximating the parameters that describe the phase transitional behaviour (similar in some sense to the transition in Physics between solid and liquid state) of two important computational problems: that of deciding whether a graph is colourable using only three colours so that no two adjacent vertices receive the same colour, and that of deciding whether a propositional boolean formula in conjunctive normal form with clauses containing at most three literals is satisfiable. A specific notion of maximal solution and, for the second problem, the use of a probabilistic model called the (young) coupon collector allows us to improve the best known results for these problems. Finally we look at two graph theoretic matching problems. We first study the computational complexity of these problems and the algorithmic approximability of the optimal solutions, in particular classes of graphs. We also derive an algorithm that solves one of them optimally in linear time when the input graph is a tree as well as a number of non-approximability results. Then we make some assumptions about the input distribution, we study the expected structure of these matchings and we derive improved approximation results on several models of random graphs.

Item Type: Thesis or Dissertation (PhD)
Subjects: Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions: Faculty of Science > Computer Science
Library of Congress Subject Headings (LCSH): Combinatorial analysis, Graph theory
Publisher: Department of Computer Science
Place of Publication: Coventry, UK
Official Date: November 1999
Dates:
DateEvent
November 1999Submitted
DOI: CS-RR-369
Institution: University of Warwick
Theses Department: Department of Computer Science
Thesis Type: PhD
Publication Status: Published
Supervisor(s)/Advisor: Gibbons, Alan (Alan M.)
Extent: ix, 141 p.
Language: eng

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us