Graphs Algorithms and Optimization Second Edition by William Kocay 1482251256 9781482251258

Graphs Algorithms and Optimization Second Edition by William Kocay – Ebook Instant Download/Delivery ISBN(s): 1482251256,  9781482251258

Product details:

• ISBN 10: 1482251256
• ISBN 13: 9781482251258
• Author: William

The second edition of this popular book presents the theory of graphs from an algorithmic viewpoint. The authors present the graph theory in a rigorous, but informal style and cover most of the main areas of graph theory. The ideas of surface topology are presented from an intuitive point of view. We have also included a discussion on linear programming that emphasizes problems in graph theory. The text is suitable for students in computer science or mathematics programs.

Table of contents:

1 Graphs and Their Complements
1.1 Introduction
Exercises
1.2 Degree sequences
1.2.1 Havel-Hakimi theorem
1.2.2 Erdös-Gallai theorem
Exercises
1.3 Analysis
Exercises
1.4 Notes
2 Paths and Walks
2.1 Introduction
2.2 Complexity
Exercises
2.3 Walks
Exercises
2.4 The shortest-path problem
2.5 Weighted graphs and Dijkstra’s algorithm
Exercises
2.6 Data structures
2.7 Floyd’s algorithm
Exercises
2.8 Notes
3 Subgraphs
3.1 Counting subgraphs
3.1.1 Möbius inversion
3.1.2 Counting triangles
3.2 Multiplying subgraph counts
3.3 Mixed subgraphs
3.4 Graph reconstruction
3.4.1 Nash-Williams’ lemma
Exercises
3.5 Notes
4 Some Special Classes of Graphs
4.1 Bipartite graphs
Exercises
4.2 Line graphs
Exercises
4.3 Moore graphs
Exercises
4.4 Euler tours
4.4.1 An Euler tour algorithm
Exercises
4.5 Notes
5 Trees and Cycles
5.1 Introduction
Exercises
5.2 Fundamental cycles
Exercises
5.3 Co-trees and bonds
Exercises
5.4 Spanning tree algorithms
5.4.1 Prim’s algorithm
5.4.1.1 Data structures
Exercises
5.4.2 Kruskal’s algorithm
5.4.2.1 Data structures and complexity
5.4.3 The Cheriton-Tarjan algorithm
Exercises
5.4.4 Leftist binary trees
Exercises
5.5 Notes
6 The Structure of Trees
6.1 Introduction
6.2 Non-rooted trees
Exercises
6.3 Read’s tree encoding algorithm
6.3.1 The decoding algorithm
Exercises
6.4 Generating rooted trees
Exercises
6.5 Generating non-rooted trees
Exercises
6.6 Prüfer sequences
6.7 Spanning trees
6.8 The matrix-tree theorem
Exercises
6.9 Notes
7 Connectivity
7.1 Introduction
Exercises
7.2 Blocks
7.3 Finding the blocks of a graph
Exercises
7.4 The depth-first search
7.4.1 Complexity
Exercises
7.5 Sections and modules
Exercises
7.6 Notes
8 Graphs and Symmetry
8.1 Groups
8.2 Cayley graphs
8.3 Coset diagrams
8.3.1 Double cosets
8.4 Conjugation, Sylow subgroups
8.5 Homomorphisms
8.6 Primitivity and block systems
Exercises
8.7 Self-complementary graphs
8.8 Pseudo-similar vertices
Exercises
8.9 Notes
9 Alternating Paths and Matchings
9.1 Introduction
Exercises
9.2 The Hungarian algorithm
9.2.1 Complexity
Exercises
9.3 Edmonds’ algorithm, blossoms
9.3.1 Complexity
9.4 Perfect matchings and 1-factorizations
Exercises
9.5 The subgraph problem
9.6 Coverings in bipartite graphs
9.7 Tutte’s theorem
Exercises
9.8 Notes
10 Network Flows
10.1 Introduction
10.2 The Ford-Fulkerson algorithm
Exercises
10.3 Matchings and flows
Exercises
10.4 Menger’s theorems
Exercises
10.5 Disjoint paths and separating sets
Exercises
10.6 Notes
11 Hamilton Cycles
11.1 Introduction
Exercises
11.2 The crossover algorithm
11.2.1 Complexity
Exercises
11.3 The Hamilton closure
Exercises
11.4 The extended multi-path algorithm
11.4.1 Data structures for the segments
Exercises
11.5 Decision problems, NP-completeness
Exercises
11.6 The traveling salesman problem
Exercises
11.7 The ΔTSP
11.8 Christofides’ algorithm
Exercises
11.9 Notes
12 Digraphs
12.1 Introduction
12.2 Activity graphs, critical paths
12.3 Topological order
Exercises
12.4 Strong components
Exercises
12.4.1 An application to fabrics
Exercises
12.5 Tournaments
12.5.1 Modules
Exercises
12.6 2-Satisfiability
Exercises
12.7 Notes
13 Graph Colorings
13.1 Introduction
13.1.1 Intersecting lines in the plane
Exercises
13.2 Cliques
13.3 Mycielski’s construction
13.4 Critical graphs
Exercises
13.5 Chromatic polynomials
Exercises
13.6 Edge colorings
Exercises
13.7 Graph homomorphisms
Exercises
13.8 NP-completeness
13.9 Notes
14 Planar Graphs
14.1 Introduction
14.2 Jordan curves
14.3 Graph minors, subdivisions
Exercises
14.4 Euler’s formula
14.5 Rotation systems
14.6 Dual graphs
14.7 Platonic solids, polyhedra
Exercises
14.8 Triangulations
14.9 The sphere
Exercises
14.10 Whitney’s theorem
14.11 Medial digraphs
Exercises
14.12 The 4-color problem
14.13 Nowhere-zero flows
Exercises
14.14 Straight-line drawings
14.15 Coordinate averaging
14.16 Kuratowski’s theorem
Exercises
14.17 The Hopcroft-Tarjan algorithm
14.17.1 Bundles
14.17.2 Switching bundles
14.17.3 The general Hopcroft-Tarjan algorithm
14.18 Notes
15 Graphs and Surfaces
15.1 Introduction
15.2 Surfaces
15.2.1 Handles and crosscaps
15.2.2 The Euler characteristic and genus of a surface
Exercises
15.3 Isometries of surfaces
Exercises
15.4 Graph embeddings, obstructions
15.5 Graphs on the torus
Exercises
15.5.1 Platonic maps on the torus
15.5.2 Drawing torus maps, triangulations
Exercises
15.6 Coordinate averaging
15.7 Graphs on the projective plane
15.7.1 The facewidth
15.7.2 Double covers
Exercises
15.8 Embedding algorithms
Exercises
15.9 Heawood’s map coloring theorem
Exercises
15.10 Notes
16 The Klein Bottle and the Double Torus
16.1 The Klein bottle
16.1.1 Rotation systems
16.1.2 The double cover
Exercises
16.2 The double torus
16.2.1 Isometries of the hyperbolic plane
Exercises
16.2.2 The double torus as an octagon
Exercises
16.3 Notes
17 Linear Programming
17.1 Introduction
17.1.1 A simple example
17.1.2 Simple graphical example
17.1.3 Slack and surplus variables
Exercises
17.2 The simplex algorithm
17.2.1 Overview
17.2.2 Some notation
17.2.3 Phase 0: finding a basis solution
17.2.4 Obtaining a basis feasible solution
17.2.5 The tableau
17.2.6 Phase 2: improving a basis feasible solution
17.2.7 Unbounded solutions
17.2.8 Conditions for optimality
17.2.9 Phase 1: initial basis feasible solution
17.2.10 An example
17.3 Cycling
Exercises
17.4 Notes
18 The Primal-Dual Algorithm
18.1 Introduction
18.2 Alternate form of the primal and its dual
18.3 Geometric interpretation
18.3.1 Example
18.4 Complementary slackness
18.5 The dual of the shortest-path problem
Exercises
18.6 The primal-dual algorithm
18.6.1 Initial feasible solution
18.6.2 The shortest-path problem
18.6.3 Maximum flow
Exercises
18.7 Notes
19 Discrete Linear Programming

People also search:

latin-american algorithms graphs and optimization symposium

types of optimization algorithms

list of optimization algorithms

optimal algorithm example

latest optimization algorithms