| Titre : |
Graph Searching Games and Probabilistic Methods |
| Type de document : |
texte imprimé |
| Auteurs : |
Anthony Bonato, Auteur ; Pawel Pralat, Auteur |
| Mention d'édition : |
1éd. |
| Editeur : |
Francis :CRC Press |
| Année de publication : |
2018 |
| Importance : |
379p. |
| Présentation : |
Couverture externe,figures |
| Format : |
24X16cm |
| ISBN/ISSN/EAN : |
978-1-138-62716-1 |
| Note générale : |
List of Figures
List of Tables
Bibliography:p.357
Index:p.375
Dr. Anthony Bonato is a professor of Mathematics at Ryerson University, whose main research interests are in graph theory and complex networks. He is co-Editor-in-Chief of Internet Mathematics, editor for Contributions to Discrete Mathematics, and Chair of the Pure Mathematics group within the NSERC Discovery Grants Mathematics and Statistics Evaluation Group.
Dr. Pawel Präat is an associate professor at Ryerson University whose main research interests are in graph theory and complex networks. He is the Assistant Director of Industry Liaison at The Fields Institute for Research in Mathematical Sciences, and has pursued collaborations with various industry partners as well as the Government of Canada. |
| Langues : |
Anglais moyen (ca.1100-1500) (enm) Langues originales : Anglais moyen (ca.1100-1500) (enm) |
| Catégories : |
2 Science
|
| Mots-clés : |
Graphs,probability |
| Index. décimale : |
519 |
| Résumé : |
Graph Searching Games and Probabilistic Methods is the first book that focuses on the intersection of graph searching games and probabilistic methods. The book explores various applications of these powerful mathematical tools to games and processes such as Cops and Robbers, Zombie and Survivors, and Firefighting. Written in an engaging style, the book is accessible to a wide audience including mathematicians and computer scientists. Readers will find that the book provides state-of-the-art results, techniques, and directions in graph searching games, especially from the point of view of probabilistic methods. The authors describe three directions while providing numerous examples, which include: • Playing a deterministic game on a random board. • Players making random moves. • Probabilistic methods used to analyze a deterministic game. |
| Note de contenu : |
Preface
1 Introduction
1.1 Graphs
1.2 Probability
1.3 Asymptotic Notation and Useful Inequalities
1.4 Random Graphs
1.5 Tools: First and Second Moment Methods
1.6 Tools: Chernoff Bounds
2 The game of Cops and Robbers
2.1 Binomial Random Graphs
2.2 Graphs with a Given Cop Number
2.3 Properties of Almost All Cop-Win Graphs
2.4 Properties of Almost All k-Cop-Win Graphs
2.5 Random Geometric Graphs
2.6 Percolated Random Geometric Graphs
3 Variations of Cops and Robbers
3.1 Playing on Edges
3.2 Cops and Fast Robbers
3.3 Lazy Cops and Robbers
3.4 Cops and Falling Robbers
3.5 Containment Game
4 Zombies and Survivors
4.1 The Cost of Being Undead Can Be High
4.2 Cycles
4.3 Hypercubes
4.4 Toroidal Grids
5 Large cop number and Meyniel’s conjecture
5.1 Upper Bounds for c(n)
5.2 Binomial Random Graphs
5.3 Random d-Regular Graphs
5.4 Meyniel Extremal Families
6 Graph cleaning
6.1 Tools: Convergence of Moments Method
6.2 Binomial Random Graphs
6.3 Tools: Pairing Model
6.4 Random Regular Graphs
6.5 Tools: Differential Equation Method
6.6 DE Method in Graph Cleaning
6.7 Game Brush Number
7 Acquaintance time
7.1 Dense Binomial Random Graphs
7.2 Sparse Binomial Random Graphs
7.3 Is the Upper Bound Tight?
7.4 Hypergraphs
7.5 Random Geometric Graphs
8 Firefighting
8.1 Tool: Expander Mixing Lemma
8.2 The Case
8.3 The Case
8.4 Fighting Constrained Fires in Graphs
9 Acquisition Number
9.1 Binomial Random Graphs
9.2 Random Geometric Graphs
9.3 Randomly Weighted Path
10 Temporal parameters
10.1 Capture Time
10.2 Overprescribed Cops and Robbers
10.3 Deterministic Burning
10.4 Random Burning
10.5 Cops and Drunk (but Visible) Robbers
10.6 Cops and Drunk (and Invisible) Robbers
11 Miscellaneous topics
11.1 Toppling Number
11.2 Revolutionary and Spies
11.3 Robot Crawler
11.4 Seepage |
Graph Searching Games and Probabilistic Methods [texte imprimé] / Anthony Bonato, Auteur ; Pawel Pralat, Auteur . - 1éd. . - [S.l.] : Francis :CRC Press, 2018 . - 379p. : Couverture externe,figures ; 24X16cm. ISBN : 978-1-138-62716-1 List of Figures
List of Tables
Bibliography:p.357
Index:p.375
Dr. Anthony Bonato is a professor of Mathematics at Ryerson University, whose main research interests are in graph theory and complex networks. He is co-Editor-in-Chief of Internet Mathematics, editor for Contributions to Discrete Mathematics, and Chair of the Pure Mathematics group within the NSERC Discovery Grants Mathematics and Statistics Evaluation Group.
Dr. Pawel Präat is an associate professor at Ryerson University whose main research interests are in graph theory and complex networks. He is the Assistant Director of Industry Liaison at The Fields Institute for Research in Mathematical Sciences, and has pursued collaborations with various industry partners as well as the Government of Canada. Langues : Anglais moyen (ca.1100-1500) ( enm) Langues originales : Anglais moyen (ca.1100-1500) ( enm)
| Catégories : |
2 Science
|
| Mots-clés : |
Graphs,probability |
| Index. décimale : |
519 |
| Résumé : |
Graph Searching Games and Probabilistic Methods is the first book that focuses on the intersection of graph searching games and probabilistic methods. The book explores various applications of these powerful mathematical tools to games and processes such as Cops and Robbers, Zombie and Survivors, and Firefighting. Written in an engaging style, the book is accessible to a wide audience including mathematicians and computer scientists. Readers will find that the book provides state-of-the-art results, techniques, and directions in graph searching games, especially from the point of view of probabilistic methods. The authors describe three directions while providing numerous examples, which include: • Playing a deterministic game on a random board. • Players making random moves. • Probabilistic methods used to analyze a deterministic game. |
| Note de contenu : |
Preface
1 Introduction
1.1 Graphs
1.2 Probability
1.3 Asymptotic Notation and Useful Inequalities
1.4 Random Graphs
1.5 Tools: First and Second Moment Methods
1.6 Tools: Chernoff Bounds
2 The game of Cops and Robbers
2.1 Binomial Random Graphs
2.2 Graphs with a Given Cop Number
2.3 Properties of Almost All Cop-Win Graphs
2.4 Properties of Almost All k-Cop-Win Graphs
2.5 Random Geometric Graphs
2.6 Percolated Random Geometric Graphs
3 Variations of Cops and Robbers
3.1 Playing on Edges
3.2 Cops and Fast Robbers
3.3 Lazy Cops and Robbers
3.4 Cops and Falling Robbers
3.5 Containment Game
4 Zombies and Survivors
4.1 The Cost of Being Undead Can Be High
4.2 Cycles
4.3 Hypercubes
4.4 Toroidal Grids
5 Large cop number and Meyniel’s conjecture
5.1 Upper Bounds for c(n)
5.2 Binomial Random Graphs
5.3 Random d-Regular Graphs
5.4 Meyniel Extremal Families
6 Graph cleaning
6.1 Tools: Convergence of Moments Method
6.2 Binomial Random Graphs
6.3 Tools: Pairing Model
6.4 Random Regular Graphs
6.5 Tools: Differential Equation Method
6.6 DE Method in Graph Cleaning
6.7 Game Brush Number
7 Acquaintance time
7.1 Dense Binomial Random Graphs
7.2 Sparse Binomial Random Graphs
7.3 Is the Upper Bound Tight?
7.4 Hypergraphs
7.5 Random Geometric Graphs
8 Firefighting
8.1 Tool: Expander Mixing Lemma
8.2 The Case
8.3 The Case
8.4 Fighting Constrained Fires in Graphs
9 Acquisition Number
9.1 Binomial Random Graphs
9.2 Random Geometric Graphs
9.3 Randomly Weighted Path
10 Temporal parameters
10.1 Capture Time
10.2 Overprescribed Cops and Robbers
10.3 Deterministic Burning
10.4 Random Burning
10.5 Cops and Drunk (but Visible) Robbers
10.6 Cops and Drunk (and Invisible) Robbers
11 Miscellaneous topics
11.1 Toppling Number
11.2 Revolutionary and Spies
11.3 Robot Crawler
11.4 Seepage |
|  |
Affiner la recherche Interroger des sources externes
