Algorithmic Graph Theory - Gibbons, Alan

Algorithm Graph Theory introduces most of the classical concepts of pure and applied graph theory (spanning trees, connectivity, genus, colourability, flows in networks, matching and transversals) and covers many of the classical theorems. Its emphasis is on algorithms and their complexity which graph problems have known efficient solutions and which are intractable.