Reading...
Play button
Play button
Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
15 Cards in this Set
- Front
- Back
|
Vertex cover
|
Find the set of vertices such that all edges in a graph touch a vertex (minimization).
|
|
|
Graph Coloring
|
Color vertices in a graph so no 2 adjacent vertices have the same color. (minimization)
|
|
|
SAT/CNF-SAT/3-SAT
|
Find a truth assignment for a given expression that makes the expression true.
|
|
|
3D Matching
|
Tries to match 3 things that are mutually interdependent.
|
|
|
Hamiltonian Circuit/Path
|
Visit every vertex in a graph and don't repeat vertices.
|
|
|
Partition
|
Split up a set so that the sum of the subset is exactly one half the sum of the whole set.
|
|
|
3-Colorability
|
Colors a graph with 3 colors?
|
|
|
Clique
|
Find the largest complete graph that is a subset of a given graph.
|
|
|
Bin Packing
|
Put things in containers, minimizing the number of containers used.
|
|
|
Knapsack
|
Maximize the value or weight of items to be put in a container of given size.
|
|
|
Traveling Salesman
|
Find the hamiltonian circuit of lowest weight.
|
|
|
Bin Packing approximation
|
Use NIFF, 4/3 OPT
|
|
|
Traveling Salesman approximation
|
Use minimum spanning tree, 2 x OPT
|
|
|
Knapsack approximation
|
OPT + 1/K
|
|
|
Graph Coloring approximation
|
Use SQ, sequential graph coloring. K + 1, where K is the maximum degree of a vertex in the graph
|
