Book contents
- Frontmatter
- Contents
- Chapter Dependencies
- Preface
- 1 Introduction
- 2 Early work on tolerance graphs
- 3 Trees, cotrees and bipartite graphs
- 4 Interval probe graphs and sandwich problems
- 5 Bitolerance and the ordered sets perspective
- 6 Unit and 50% tolerance orders
- 7 Comparability invariance results
- 8 Recognition of bounded bitolerance orders and trapezoid graphs
- 9 Algorithms on tolerance graphs
- 10 The hierarchy of classes of bounded bitolerance orders
- 11 Tolerance models of paths and subtrees of a tree
- 12 φ-tolerance graphs
- 13 Directed tolerance graphs
- 14 Open questions and further directions of research
- References
- Index of Symbols
- Index
1 - Introduction
Published online by Cambridge University Press: 11 August 2009
- Frontmatter
- Contents
- Chapter Dependencies
- Preface
- 1 Introduction
- 2 Early work on tolerance graphs
- 3 Trees, cotrees and bipartite graphs
- 4 Interval probe graphs and sandwich problems
- 5 Bitolerance and the ordered sets perspective
- 6 Unit and 50% tolerance orders
- 7 Comparability invariance results
- 8 Recognition of bounded bitolerance orders and trapezoid graphs
- 9 Algorithms on tolerance graphs
- 10 The hierarchy of classes of bounded bitolerance orders
- 11 Tolerance models of paths and subtrees of a tree
- 12 φ-tolerance graphs
- 13 Directed tolerance graphs
- 14 Open questions and further directions of research
- References
- Index of Symbols
- Index
Summary
Background and motivation
Our mathematical adventure begins with a collection of intervals on the real line. The intervals may have come from an application, for example, they could represent the durations of a set of events on a time line, or fragments of DNA on the genome, or sectors of consecutive elements of a linearly ordered set. Some of the intervals may intersect one another, and others may be disjoint. No matter what they may represent, intervals are familiar to us as mathematical entities. There are many relationships between these intervals that we could study. In this book, we deal mostly with intersection.
When two intervals intersect, we might interpret this positively as their having something important in common, like an opportunity to share information. For example, if each interval represented the time period during which a group of school children would be visiting a science museum, then two groups whose intervals intersect could participate in a joint activity. We might then ask, how many times would we need to flash the new Artificial Bolt of Lightning so that each group would get to see it? Or we might interpret intersection negatively as having a major conflict, like competing for a resource that cannot be shared. For example, in a one-television household, when a parent wants to watch the News and at the same time a teenager wants to watch an old movie on a different channel, we have a temporal conflict.
- Type
- Chapter
- Information
- Tolerance Graphs , pp. 1 - 28Publisher: Cambridge University PressPrint publication year: 2004
- 1
- Cited by