Graphs, Algorithms, and Optimization
1st Edition
Published on 29. November 2004
Book
Hardback
504 pages
978-1-58488-396-8 (ISBN)
Description
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.
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.
More details
Series
Language
English
Place of publication
United States
Publishing group
Taylor & Francis Inc
Target group
College/higher education
Computer science students and professionals, computer engineering students and professionals, mathematics and applied mathematics students and professionals; electrical engineers, operations research professors
Illustrations
247 s/w Tabellen, 247 s/w Abbildungen
247 Tables, black and white; 247 Illustrations, black and white
Dimensions
Height: 235 mm
Width: 159 mm
Weight
839 gr
ISBN-13
978-1-58488-396-8 (9781584883968)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Other editions
New editions
William Kocay | Donald L. Kreher
Graphs, Algorithms, and Optimization
Book
09/2016
2nd Edition
Chapman & Hall/CRC
€133.70
Article not available for order
Additional editions
Kenneth H. Rosen
Graphs, Algorithms, and Optimization
E-Book
09/2017
Chapman and Hall
€51.49
Available for download
Kenneth H. Rosen
Graphs, Algorithms, and Optimization
E-Book
09/2017
Chapman and Hall
€51.49
Available for download
Persons
Content
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
Pruefer 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
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
Pruefer 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