Tolerance graphs

Martin Charles Golumbic, Ann N. Trenk - Collection Cambridge Studies in Advanced Mathematics

278 pages, parution le 15/02/2004

Ajouter à une liste

Indisponible

Résumé

The study of algorithmic graph theory and structured families of graphs is an important branch of discrete mathematics. It finds numerous applications, from data transmission through networks to efficiently scheduling aircraft and crews, as well as contributing to breakthroughs in genetic analysis and studies of the brain. Especially important have been the theory and applications of new intersection graph models such as generalizations of permutation graphs and interval graphs. One of these is the study of tolerance graphs and tolerance orders. This book contains the first thorough study of tolerance graphs and related topics, indeed the authors have included proofs of major results previously unpublished in book form. It will act as a springboard for researchers, and especially graduate students, to pursue new directions of investigation. With many examples and exercises it is also suitable for use as the text for a graduate course in graph theory.

Sommaire

Introduction
Early work on tolerance graphs
Trees, cotrees and bipartite graphs
Interval probe graphs
Bitolerance graphs and ordered sets
Unit and 50% tolerance graphs
Comparability and invariance results
Bounded bitolerance recognition
Algorithms on tolerance graphs
The hierarchy of bitolerance orders
Tolerance models on trees
Phi-tolerance models
Directed tolerance graphs
Open questions and further directions.

Voir tout

Replier

Caractéristiques techniques

	PAPIER
Éditeur(s)	Cambridge University Press
Auteur(s)	Martin Charles Golumbic, Ann N. Trenk
Collection	Cambridge Studies in Advanced Mathematics
Parution	15/02/2004
Nb. de pages	278
Format	16 x 23,5
Couverture	Relié
Poids	568g
Intérieur	Noir et Blanc
EAN13	9780521827584
ISBN13	978-0-521-82758-4