Graphs, Algorithms, and Optimization

Note: Supplemental materials are not guaranteed with Rental or Used book purchases.

ISBN: 9781584883968 | 1584883960
Cover: Hardcover
Copyright: 11/29/2004

Sorry, this item is currently not available.

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

(22)

Introduction

(7)

Exercises

(2)

Degree sequences

(10)

Exercises

(1)

Analysis

(4)

Exercises

(1)

Notes

(1)

Paths and Walks

(24)

Introduction

(4)

Complexity

(1)

Exercises

(1)

Walks

(2)

Exercises

(1)

The shortest-path problem

(3)

Weighted graphs and Dijkstra's algorithm

(4)

Exercises

(1)

Data structures

(5)

Floyd's algorithm

(3)

Exercises

(1)

Notes

(2)

Some Special Classes of Graphs

(16)

Bipartite graphs

(3)

Exercises

(1)

Line graphs

(2)

Exercises

(1)

Moore graphs

(6)

Exercises

(1)

Euler tours

(4)

An Euler tour algorithm

(3)

Exercises

(1)

Notes

(1)

Trees and Cycles

(26)

Introduction

(2)

Exercises

(1)

Fundamental cycles

(2)

Exercises

(2)

Co-trees and bonds

(3)

Exercises

(1)

Spanning tree algorithms

(17)

Prim's algorithm

(2)

Data structures

(1)

Exercises

(1)

Kruskal's algorithm

(1)

Data structures and complexity

(1)

The Cheriton-Tarjan algorithm

(1)

Exercises

(1)

Leftist binary trees

(7)

Exercises

(1)

Notes

(2)

The Structure of Trees

(30)

Introduction

(1)

Non-rooted trees

(2)

Exercises

(1)

Read's tree encoding algorithm

(5)

The decoding algorithm

(1)

Exercises

(1)

Generating rooted trees

(8)

Exercises

105

(1)

Generating non-rooted trees

105

(1)

Exercises

106

(1)

Prufer sequences

106

(3)

Spanning trees

109

(2)

The matrix-tree theorem

111

(6)

Exercises

116

(1)

Notes

117

(2)

Connectivity

119

(20)

Introduction

119

(3)

Exercises

121

(1)

Blocks

122

(3)

Finding the blocks of a graph

125

(3)

Exercises

128

(1)

The depth-first search

128

(9)

Complexity

135

(1)

Exercises

136

(1)

Notes

137

(2)

Alternating Paths and Matchings

139

(22)

Introduction

139

(9)

Exercises

143

(1)

The Hungarian algorithm

143

(4)

Complexity

147

(1)

Exercises

148

(1)

Perfect matchings and I-factorizations

148

(4)

Exercises

151

(1)

The subgraph problem

152

(2)

Coverings in bipartite graphs

154

(1)

Tutte's theorem

155

(3)

Exercises

158

(1)

Notes

158

(3)

Network flows

161

(26)

Introduction

161

(4)

The Ford-Fulkerson algorithm

165

(11)

Exercises

175

(1)

Matchings and flows

176

(2)

Exercises

177

(1)

Menger's theorems

178

(2)

Exercises

180

(1)

Disjoint paths and separating sets

180

(5)

Exercises

183

(2)

Notes

185

(2)

Hamilton Cycles

187

(36)

Introduction

187

(4)

Exercises

190

(1)

The crossover algorithm

191

(6)

Complexity

193

(3)

Exercises

196

(1)

The Hamilton closure

197

(3)

Exercises

199

(1)

The extended multi-path algorithm

200

(5)

Data structures for the segments

204

(1)

Exercises

204

(1)

Decision problems, NP-completeness

205

(9)

Exercises

213

(1)

The traveling salesman problem

214

(2)

Exercises

216

(1)

The ΔTSP

216

(2)

Christofides' algorithm

218

(3)

Exercises

220

(1)

Notes

221

(2)

Digraphs

223

(22)

Introduction

223

(1)

Activity graphs, critical paths

223

(2)

Topological order

225

(4)

Exercises

228

(1)

Strong components

229

(9)

Exercises

230

(6)

An application to fabrics

236

(1)

Exercises

236

(2)

Tournaments

238

(2)

Exercises

240

(1)

2-Satisfiability

240

(3)

Exercises

243

(1)

Notes

243

(2)

Graph Colorings

245

(30)

Introduction

245

(4)

Intersecting lines in the plane

247

(1)

Exercises

248

(1)

Cliques

249

(4)

Mycielski's construction

253

(1)

Critical graphs

254

(2)

Exercises

255

(1)

Chromatic polynomials

256

(2)

Exercises

258

(1)

Edge colorings

258

(11)

Complexity

268

(1)

Exercises

269

(1)

NP-completeness

269

(5)

Notes

274

(1)

Planar Graphs

275

(52)

Introduction

275

(1)

Jordan curves

276

(1)

Graph minors, subdivisions

277

(5)

Exercises

282

(1)

Euler's formula

282

(2)

Rotation systems

284

(2)

Dual graphs

286

(4)

Platonic solids, polyhedra

290

(2)

Exercises

291

(1)

Triangulations

292

(3)

The sphere

295

(2)

Whitney's theorem

297

(3)

Medial digraphs

300

(1)

Exercises

301

(1)

The 4-color problem

301

(4)

Exercises

305

(1)

Straight-line drawings

305

(4)

Kuratowski's theorem

309

(3)

Exercises

312

(1)

The Hopcroft-Tarjan algorithm

312

(13)

Bundles

316

(2)

Switching bundles

318

(3)

The general Hopcroft-Tarjan algorithm

321

(4)

Notes

325

(2)

Graphs and Surfaces

327

(60)

Introduction

327

(2)

Surfaces

329

(12)

Handles and crosscaps

336

(1)

The Euler characteristic and genus of a surface

337

(3)

Exercises

340

(1)

Graph embeddings, obstructions

341

(1)

Graphs on the torus

342

(15)

Exercises

349

(1)

Platonic maps on the torus

349

(3)

Drawing torus maps, triangulations

352

(5)

Exercises

357

(1)

Graphs on the projective plane

357

(15)

The facewidth

364

(4)

Double covers

368

(2)

Exercises

370

(2)

Embedding algorithms

372

(10)

Exercises

381

(1)

Heawood's map coloring theorem

382

(3)

Exercises

384

(1)

Notes

385

(2)

Linear Programming

387

(30)

Introduction

387

(8)

A simple example

387

(2)

Simple graphical example

389

(2)

Slack and surplus variables

391

(3)

Exercises

394

(1)

The simplex algorithm

395

(18)

Overview

395

(1)

Some notation

395

(1)

Phase 0: finding a basis solution

396

(1)

Obtaining a basis feasible solution

397

(1)

The tableau

398

(1)

Phase 2: improving a basis feasible solution

399

(4)

Unbounded solutions

403

(2)

Conditions for optimality

405

(2)

Phase 1: initial basis feasible solution

407

(4)

An example

411

(2)

Cycling

413

(3)

Exercises

415

(1)

Notes

416

(1)

The Primal-Dual Algorithm

417

(32)

Introduction

417

(6)

Alternate form of the primal and its dual

423

(1)

Geometric interpretation

424

(5)

Example

424

(5)

Complementary slackness

429

(1)

The dual of the shortest-path problem

430

(4)

Exercises

433

(1)

The primal-dual algorithm

434

(12)

Initial feasible solution

437

(3)

The shortest-path problem

440

(4)

Maximum flow

444

(2)

Exercises

446

(1)

Notes

446

(3)

Discrete Linear Programming

449

(20)

Introduction

449

(1)

Backtracking

450

(3)

Branch and bound

453

(12)

Exercises

463

(2)

Unimodular matrices

465

(3)

Exercises

467

(1)

Notes

468

(1)

Bibliography

469

(8)

Index

477

Please wait while the item is added to your bag...

FREE SHIPPING

Amazon no longer offers textbook rentals. We do!

Graphs, Algorithms, and Optimization

Summary

Table of Contents

Supplemental Materials