Algorithmic graph theory and perfect graphs

Martin Charles Golumbic - Collection Annals of discrete mathematics

314 pages, parution le 06/05/2004 (2^eme édition)

Ajouter à une liste

Indisponible

Résumé

Research in graph theory and its applications has increased considerably in recent years. Typically, the elaboration of new theoretical structures has motivated a search for new algorithms compatible with those structures. Rather than the arduous and systematic study of every new concept definable with a graph, the main task for the mathematician is to eliminate the often arbitrary and cumbersome definitions, keeping only the "deep" mathematical problems.

This book, by Martin Golumbic, is intended as an introduction to graph theory through just these practical problems, nearly all of them related to the structure of permutation graphs, interval graphs, circle graphs, threshold graphs, perfect graphs, and others.

The reader will not find motivations drawn from number theory, as is usual for most of the extremal graph problems, or from such refinements of old riddles as the four-color problem and the Hamiltonian tour. Instead, Golumbic has selected practical problems that occur in operations research, scheduling, econometrics, and even genetics or ecology.

Sommaire

Graph theoretic foundations
The design of efficient algorithms
Perfect graphs
Triangulated graphs
Comparability graphs
Split graphs
Permutation graphs
Interval graphs
Superperfect graphs
Threshold graphs
Not so perfect graphs
Perfect Gaussian elimination

Voir tout

Replier

Caractéristiques techniques

	PAPIER
Éditeur(s)	Elsevier
Auteur(s)	Martin Charles Golumbic
Collection	Annals of discrete mathematics
Parution	06/05/2004
Édition	2^eme édition
Nb. de pages	314
Format	17 x 24,5
Couverture	Relié
Poids	761g
Intérieur	Noir et Blanc
EAN13	9780444515308
ISBN13	978-0-444-51530-8