Package roadmap #14
Description
Polynomial problems
- shortest path
- flow
- assignment / matching
- spanning tree
NP-hard problems
- coloring
- fractional coloring (see Optimal proper coloring, chromatic number, fractional chromatic number #5)
- vertex / edge cover
- maximum clique / independent set
- traveling salesperson
- graph isomorphism
See also: