A Stochastic Model for Networks that Arise from Conference Scheduling Problems Open Access

Celis, Andres (2015)

Permanent URL: https://etd.library.emory.edu/concern/etds/n583xv06q?locale=en


A conference scheduling problem may be viewed as an undirected graph whose vertices correspond to the events of the conference, and whose edges correspond to constraints that prohibit two events from being scheduled at the same time. In this thesis we propose and analyze a new random graph model inspired by a series of experimental observations on datasets from the industry, as well as conversations with a conference scheduler. Our models differs from existing random graph models in the following:

1. We find that graph models with independently chosen edges do not result in degree distributions found in conference scheduling problems. Thus our model's edges are statistically dependent on each other.

2. Our model introduces new vertices into the graph as time evolves. The existing models that do this have small, bounded clique and chromatic numbers and are trivial to color, which is not an accurate representation of scheduling problems. We show that the expected clique number of our model has a lower bound of Ω (T1/4/(log T)3/4). We also argue that the expected clique and chromatic numbers of our model are upper bounded by O(T1/4) and O(T2/5), respectively.

Table of Contents

1 Introduction...1

2 Graph Coloring and Existing Graph Models...3

2.1 Graph Coloring...3

2.2 Erdos-Rényi Model...4

2.3 Barabási-Albert Model...5

2.4 Evolving Copying Model...5

2.5 Coloring Algorithms...6

2.5.1 Greedy...6

2.5.2 DSATUR...7

2.5.3 RLF...7

2.5.4 Ex-DSATUR...8

3 Haws Model...9

3.1 General Description...9

3.2 Construction Process and Choosing Edges...11

4 Analysis of Haws Model and Future Work...14

4.1 Experimental Results...14

4.1.1 Degree Distribution Results...14

4.1.2 Clique and Chromatic Number Results...18

4.2 Analysis...30

4.2.1 The Triangle Model...30

4.2.2 Degree Estimates...32

4.2.3 Lower Bounds...32

4.2.4 Upper Bounds...33

4.3 Summary and Future Work...34


5.1 Haws Model Graph Generator...36

5.2 Usage...40


About this Master's Thesis

Rights statement
  • Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.
  • English
Research Field
Committee Chair / Thesis Advisor
Committee Members
Last modified

Primary PDF

Supplemental Files