Graphs, Algorithms, and Optimization

Graphs, Algorithms, and Optimization

  • Electronic book text
By (author)  , By (author) 

List price: US$132.96

Currently unavailable

We can notify you when this item is back in stock

Add to wishlist

AbeBooks may have this title (opens in new window).

Try AbeBooks

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.show more

Product details

  • Electronic book text | 504 pages
  • Taylor & Francis Ltd
  • Chapman & Hall/CRC
  • United States
  • 247 Tables, black and white; 247 Illustrations, black and white
  • 0203489055
  • 9780203489055

Table of contents

GRAPHS AND THEIR COMPLEMENTSDegree sequencesAnalysisPATHS AND WALKSComplexity WalksThe shortest path problemWeighted graphs and Dijkstra's algorithmData structures. Floyd's algorithmSOME SPECIAL CLASSES OF GRAPHSBipartite graphsLine graphsMoore graphsEuler toursTREES AND CYCLESFundamentalCo-trees and bondsSpanning tree algorithmsTHE STRUCTURE OF TREESNon-rootedRead's tree encoding algorithmGenerating rooted treesGenerating non-rooted trees Prufer sequencesSpanning treesThe matrix-tree theoremCONNECTIVITYBlocksFinding the blocks of a graphThe depth-first searchALTERNATING PATHS AND MATCHINGS. The Hungarian algorithmPerfect matchings and 1-factorizationsThe subgraph problemCoverings in bipartite graphsTutte's theoremNETWORK FLOWSIntroductionThe Ford-Fulkerson algorithmMatchings and flowsMenger's theoremsDisjoint paths and separating setsNotesHAMILTON CYCLESThe crossover algorithmThe Hamilton closureThe extended multi-path algorithmThe traveling salesman problemThe ?TSPChristofides' algorithmDIGRAPHSActivity graphs, Critical pathsTopological orderStrong componentsAn application to fabricsTournamentsSatisfiabilityGRAPH COLORINGSCliquesMycielski's constructionCritical graphsChromatic polynomialsEdge coloringsNP-completenessPLANAR GRAPHSJordan curvesGraph minors SubdivisionsEuler's formulaRotation systemsDual graphsPlatonic solidsTriangulationsThe sphere 5Whitney's theoremMedial digraphsThe 4-color problemStraight line drawingsKuratowski's theoremThe Hopcroft-Tarjan AlgorithmGRAPHS AND SURFACESSurfacesGraph embeddingsGraphs on the torusGraphs on the projective planeLINEAR PROGRAMMINGThe simplex algorithmCyclingTHE PRIMAL-DUAL ALGORITHMAlternate form of the primal and its dualGeometric interpretationComplementary slacknessThe dual of the shortest path problemThe primal-dual algorithmDISCRETE LINEAR PROGRAMMINGBacktrackingBranch and boundUnimodular matricesBIBLIOGRAPHYINDEXshow more