[+]
Graph Problems. Vertex Cover: planar maxdegree3; exact vertex cover (polynomial), edge cover (polynomial), connected vertex cover, rectilinear Steiner tree. Vertex Coloring: planar maxdegree4 3coloring, maxdegree3 3coloring (polynomial), Push1X, Push1G (gravity). Graph Orientation: 1in3, 2in3, 0or3 vertices; packing trominoes. Graph Layout: Bandwidth, minimum linear arrangement, cutwidth, vertex separation, sum cut, edge bisection, vertex bisection; betweenness; bipartite crossing number, crossing number, Rubik's Cube. 

This lecture is our last about straightup NPhardness. We've already seen the main techniques for such proofs, but there are a few other techniques that get used now and then. We will see three:

Handwritten notes, page 1/7 •
[previous page] •
[next page] •
[PDF]
Handwritten notes, page 1/7 • [previous page] • [next page] • [PDF] 

Slides, page 1/31 •
[previous page] •
[next page] •
[PDF]
http://dx.doi.org/10.1137/0211025 Slides, page 1/31 • [previous page] • [next page] • [PDF] 