Nicht aus der Schweiz? Besuchen Sie lehmanns.de
Graphs, Algorithms, and Optimization - William Kocay, Donald L. Kreher

Graphs, Algorithms, and Optimization

Buch | Hardcover
504 Seiten
2004
Chapman & Hall/CRC (Verlag)
978-1-58488-396-8 (ISBN)
CHF 165,80 inkl. MwSt
zur Neuauflage
  • Titel erscheint in neuer Auflage
  • Artikel merken
Zu diesem Artikel existiert eine Nachauflage
Features an explanation of modern graph theory. This title presents graph theory from an algorithmic point of view, allowing for a variety of technical applications. It includes useful programming techniques to solve graph theory problems, and applicable data structures to show how algorithms can be programmed.
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?
Mehr entdecken
aus dem Bereich
Numbers and Counting, Groups, Graphs, Orders and Lattices

von Volker Diekert; Manfred Kufleitner; Gerhard Rosenberger …

Buch | Softcover (2023)
De Gruyter (Verlag)
CHF 89,95