#### Get Citation

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

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

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

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

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

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