Graphs, Algorithms, and Optimization
Chapman & Hall/CRC (Verlag)
978-1-58488-396-8 (ISBN)
- Titel erscheint in neuer Auflage
- Artikel merken
Graph theory offers a rich source of problems and techniques for programming and data structure development, as well as for understanding computing theory, including NP-Completeness and polynomial reduction.
A comprehensive text, Graphs, Algorithms, and Optimization features clear exposition on modern algorithmic graph theory presented in a rigorous yet approachable way. The book covers major areas of graph theory including discrete optimization and its connection to graph algorithms. The authors explore surface topology from an intuitive point of view and include detailed discussions on linear programming that emphasize graph theory problems useful in mathematics and computer science. Many algorithms are provided along with the data structure needed to program the algorithms efficiently. The book also provides coverage on algorithm complexity and efficiency, NP-completeness, linear optimization, and linear programming and its relationship to graph algorithms.
Written in an accessible and informal style, this work covers nearly all areas of graph theory. Graphs, Algorithms, and Optimization provides a modern discussion of graph theory applicable to mathematics, computer science, and crossover applications.
GRAPHS AND THEIR COMPLEMENTS
Degree sequences
Analysis
PATHS AND WALKS
Complexity
Walks
The shortest path problem
Weighted graphs and Dijkstra's algorithm
Data structures. Floyd's algorithm
SOME SPECIAL CLASSES OF GRAPHS
Bipartite graphs
Line graphs
Moore graphs
Euler tours
TREES AND CYCLES
Fundamental
Co-trees and bonds
Spanning tree algorithms
THE STRUCTURE OF TREES
Non-rooted
Read's tree encoding algorithm
Generating rooted trees
Generating non-rooted trees
Prüfer sequences
Spanning trees
The matrix-tree theorem
CONNECTIVITY
Blocks
Finding the blocks of a graph
The depth-first search
ALTERNATING PATHS AND MATCHINGS.
The Hungarian algorithm
Perfect matchings and 1-factorizations
The subgraph problem
Coverings in bipartite graphs
Tutte's theorem
NETWORK FLOWS
Introduction
The Ford-Fulkerson algorithm
Matchings and flows
Menger's theorems
Disjoint paths and separating sets
Notes
HAMILTON CYCLES
The crossover algorithm
The Hamilton closure
The extended multi-path algorithm
The traveling salesman problem
The ?TSP
Christofides' algorithm
DIGRAPHS
Activity graphs, Critical paths
Topological order
Strong components
An application to fabrics
Tournaments
Satisfiability
GRAPH COLORINGS
Cliques
Mycielski's construction
Critical graphs
Chromatic polynomials
Edge colorings
NP-completeness
PLANAR GRAPHS
Jordan curves
Graph minors
Subdivisions
Euler's formula
Rotation systems
Dual graphs
Platonic solids
Triangulations
The sphere 5
Whitney's theorem
Medial digraphs
The 4-color problem
Straight line drawings
Kuratowski's theorem
The Hopcroft-Tarjan Algorithm
GRAPHS AND SURFACES
Surfaces
Graph embeddings
Graphs on the torus
Graphs on the projective plane
LINEAR PROGRAMMING
The simplex algorithm
Cycling
THE PRIMAL-DUAL ALGORITHM
Alternate form of the primal and its dual
Geometric interpretation
Complementary slackness
The dual of the shortest path problem
The primal-dual algorithm
DISCRETE LINEAR PROGRAMMING
Backtracking
Branch and bound
Unimodular matrices
BIBLIOGRAPHY
INDEX
| Erscheint lt. Verlag | 29.11.2004 |
|---|---|
| Reihe/Serie | Discrete Mathematics and Its Applications |
| Zusatzinfo | 247 Tables, black and white; 247 Illustrations, black and white |
| Sprache | englisch |
| Maße | 156 x 234 mm |
| Gewicht | 839 g |
| Themenwelt | Mathematik / Informatik ► Mathematik ► Graphentheorie |
| ISBN-10 | 1-58488-396-0 / 1584883960 |
| ISBN-13 | 978-1-58488-396-8 / 9781584883968 |
| Zustand | Neuware |
| Haben Sie eine Frage zum Produkt? |
aus dem Bereich
