Graphs, algorithms, and optimization

著者

• Kocay, William
• Kreher, Donald L

書誌事項

Graphs, algorithms, and optimization

William Kocay, Donald L. Kreher

（Discrete mathematics and its applications / Kenneth H. Rosen, series editor）

Chapman & Hall/CRC, c2005

• : hbk

注記

Includes bibliographical references (p. 469-476) and 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 Prufer 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

「Nielsen BookData」 より

詳細情報

• NII書誌ID(NCID): BA7029786X
• ISBN:
  • 1584883960
• LCCN: 2004056153
• 出版国コード: us
• タイトル言語コード: eng
• 本文言語コード: eng
• 出版地: Boca Raton, Fla.
• ページ数/冊数: 483 p.
• 大きさ: 25 cm
• 分類:
  • LCC : QA166.245
  • DC22 : 511/.5
• 件名:
  • LCSH : Graph algorithms
• 親書誌ID:
  • BA25247299