Expand description
Graph problems.
Problems whose input is a graph (optionally weighted):
MaximumIndependentSet: Maximum weight independent setMaximalIS: Maximal independent setMinimumVertexCover: Minimum weight vertex coverMinimumDominatingSet: Minimum dominating setMinimumFeedbackVertexSet: Minimum weight feedback vertex set in a directed graphMaximumClique: Maximum weight cliqueMaxCut: Maximum cut on weighted graphsGraphPartitioning: Minimum bisection (balanced graph partitioning)KColoring: K-vertex coloringMaximumMatching: Maximum weight matchingTravelingSalesman: Traveling Salesman (minimum weight Hamiltonian cycle)SpinGlass: Ising model HamiltonianBicliqueCover: Biclique cover on bipartite graphs
Structsยง
- Biclique
Cover - The Biclique Cover problem.
- Graph
Partitioning - The Graph Partitioning (Minimum Bisection) problem.
- KColoring
- The Graph K-Coloring problem.
- MaxCut
- The Maximum Cut problem.
- MaximalIS
- The Maximal Independent Set problem.
- Maximum
Clique - The MaximumClique problem.
- Maximum
Independent Set - The Independent Set problem.
- Maximum
Matching - The Maximum Matching problem.
- Minimum
Dominating Set - The Dominating Set problem.
- Minimum
Feedback Vertex Set - The Minimum Feedback Vertex Set problem.
- Minimum
Vertex Cover - The Vertex Covering problem.
- Spin
Glass - The Spin Glass (Ising model) problem.
- Traveling
Salesman - The Traveling Salesman problem.