Graph Algorithms and Combinatorial Optimization

Undergraduate

discusses classical problems in combinatorial optimization and graph algorithms, including matching, colorability, independent sets, isomorphism, network flows and scheduling. Special families of graphs are discussed and algorithms that would otherwise be NP-hard or complete are shown to be polynomial time when restricted to such families.