Details

<p>Introduction 17</p> <p><b>Chapter 1. Basic Concepts 21</b></p> <p>1.1 The origin of the graph concept 21</p> <p>1.2 Definition of graphs 24</p> <p>1.3 Subgraphs 28</p> <p>1.4 Paths and cycles 29</p> <p>1.5 Degrees 33</p> <p>1.6 Connectedness 35</p> <p>1.7 Bipartite graphs 36</p> <p>1.8 Algorithmic aspects 37</p> <p>1.9 Exercises 41</p> <p><b>Chapter 2. Trees 45</b></p> <p>2.1 Definitions and properties 45</p> <p>2.2 Spanning trees 49</p> <p>2.3 Application: minimum spanning tree problem 54</p> <p>2.4 Connectivity 59</p> <p>2.5 Exercises 66</p> <p><b>Chapter 3. Colorings 71</b></p> <p>3.1 Coloring problems 71</p> <p>3.2 Edge coloring 71</p> <p>3.3 Algorithmic aspects 73</p> <p>3.4 The timetabling problem 75</p> <p>3.5 Exercises 81</p> <p><b>Chapter 4. Directed Graphs 83</b></p> <p>4.1 Definitions and basic concepts 83</p> <p>4.2 Acyclic digraphs 90</p> <p>4.3 Arborescences 92</p> <p>4.4 Exercises 95</p> <p><b>Chapter 5. Search Algorithms 97</b></p> <p>5.1 Depth-first search of an arborescence 97</p> <p>5.2 Optimization of a sequence of decisions 103</p> <p>5.3 Depth-first search of a digraph 109</p> <p>5.4 Exercises 117</p> <p><b>Chapter 6. Optimal Paths 119</b></p> <p>6.1 Distances and shortest paths problems 119</p> <p>6.2 Case of non-weighted digraphs: breadth-first search 120</p> <p>6.3 Digraphs without circuits 125</p> <p>6.4 Application to scheduling 128</p> <p>6.5 Positive lengths 134</p> <p>6.6 Other cases 142</p> <p>6.7 Exercises 143</p> <p><b>Chapter 7. Matchings 149</b></p> <p>7.1 Matchings and alternating paths 149</p> <p>7.2 Matchings in bipartite graphs 152</p> <p>7.3 Assignment problem 156</p> <p>7.4 Optimal assignment problem 164</p> <p>7.5 Exercises 171</p> <p><b>Chapter 8. Flows 173</b></p> <p>8.1 Flows in transportation networks 173</p> <p>8.2 The max-flow min-cut theorem 177</p> <p>8.3 Maximum flow algorithm 180</p> <p>8.4 Flow with stocks and demands 188</p> <p>8.5 Revisiting theorems 191</p> <p>8.6 Exercises 194</p> <p><b>Chapter 9. Euler Tours 197</b></p> <p>9.1 Euler trails and tours 197</p> <p>9.2 Algorithms 201</p> <p>9.3 The Chinese postman problem 207</p> <p>9.4 Exercises 212</p> <p><b>Chapter 10. Hamilton Cycles 215</b></p> <p>10.1 Hamilton cycles 215</p> <p>10.2 The traveling salesman problem 218</p> <p>10.3 Approximation of a difficult problem 220</p> <p>10.4 Approximation of themetric TSP 223</p> <p>10.5 Exercises 234</p> <p><b>Chapter 11. Planar Representations 237</b></p> <p>11.1 Planar graphs 237</p> <p>11.2 Other graph representations 242</p> <p>11.3 Exercises 244</p> <p><b>Chapter 12. Problems with Comments 247</b></p> <p>12.1 Problem 1: A proof of k-connectivity 247</p> <p>12.2 Problem2: An application to compiler theory 249</p> <p>12.3 Problem3: Kernel of a digraph 251</p> <p>12.4 Problem 4: Perfect matching in a regular bipartite graph 253</p> <p>12.5 Problem5: Birkhoff-Von Neumann’s theorem 254</p> <p>12.6 Problem 6: Matchings and tilings 256</p> <p>12.7 Problem7: Strip mining 258</p> <p>Appendix A. Expression of Algorithms 261</p> <p>Appendix B. Bases of Complexity Theory 267</p> <p>Bibliography 277</p> <p>Index 279</p>

<b>Jean-Claude Fournier</b> is Professor at the University of Paris 12, France, and is a member of the Unite Mixte de Recherche Combinatoire et Optimisation (University of Paris 6 and CNRS) founded by Claude Berge.

US