|
Graphs and hypergraphs Graphs occur frequently in everyday applications. Examples include biological or social networks, which contain hundreds, thousands and even billions of nodes in some cases (see e.g. Facebook or LinkedIn). 1-planarity[1] 3-dimensional matching[2][3] Bipartite dimension[4] Capacitated minimum spanning tree[5] Route inspection problem (also called Chinese postman problem) for mixed graphs (having both directed and undirected edges). The program is solvable in polynomial time if the graph has all undirected or all directed edges. Variants include the rural postman problem.[6] Clique problem[2][7] Complete coloring, a.k.a. achromatic number[8] Domatic number[9] Dominating set, a.k.a. domination number[10] NP-complete special cases include the edge dominating set problem, i.e., the dominating set problem in line graphs. NP-complete variants include the connected dominating set problem and the maximum leaf spanning tree problem.[11] Bandwidth problem[12] Clique cover problem[2][13] Rank coloring a.k.a. cycle rank Degree-constrained spanning tree[14] Exact cover problem. Remains NP-complete for 3-sets. Solvable in polynomial time for 2-sets (this is a matching).[2][15] Feedback vertex set[2][16] Feedback arc set[2][17] Graph homomorphism problem[18] Graph coloring[2][19] Graph partition into subgraphs of specific types (triangles, isomorphic subgraphs, Hamiltonian subgraphs, forests, perfect matchings) are known NP-complete. Partition into cliques is the same problem as coloring the complement of the given graph. A related problem is to find a partition that is optimal terms of the number of edges between parts.[20] Hamiltonian completion[21] Hamiltonian path problem, directed and undirected.[2][22] Longest path problem[23] Maximum bipartite subgraph or (especially with weighted edges) maximum cut.[2][24] Maximum independent set[25] Maximum Induced path[26] Graph intersection number[27] Metric dimension of a graph[28] Minimum k-cut Minimum spanning tree, or Steiner tree, for a subset of the vertices of a graph.[2] (The minimum spanning tree for an entire graph is solvable in polynomial time.) Pathwidth[29] Set cover (also called minimum cover problem) This is equivalent, by transposing the incidence matrix, to the hitting set problem.[2][30] Set splitting problem [31] Shortest total path length spanning tree[32] Slope number two testing[33] Treewidth[29] Vertex cover[2][34] Mathematical programming 3-partition problem[35] Bin packing problem[36] Knapsack problem and several variants[2][37] Variations on the Traveling salesman problem. The problem for graphs is NP-complete if the edge lengths are assumed integers. The problem for points on the plane is NP-complete with the discretized Euclidean metric and rectilinear metric. The problem is known to be NP-hard with the (non-discretized) Euclidean metric.[38] Bottleneck traveling salesman[39] Integer programming. The variant where variables are required to be 0 or 1, called zero-one linear programming, and several other variants are also NP-complete[2][40] Numerical 3-dimensional matching[41] Partition problem[2][42] Quadratic assignment problem[43] Quadratic programming (NP-hard in some cases, P if convex) Subset sum problem[44] Formal languages and string processing Closest string[45] Longest common subsequence problem[46] The bounded variant of the Post correspondence problem[47] Shortest common supersequence[48] String-to-string correction problem[49] Games and puzzles Battleship Bulls and Cows, marketed as Master Mind Eternity II (Generalized) FreeCell[50] Fillomino[51] Heyawake[52] (Generalized) Instant Insanity[53] Kakuro (Cross Sums) Kuromasu (also known as Kurodoko)[54] Lemmings[55] Light Up[56] Masyu[57] Minesweeper Consistency Problem[58] (but see Scott, Stege, & van Rooij[59]) Nimber (or Grundy number) of a directed graph.[60] Nonograms Nurikabe SameGame (Generalized) Sudoku Super Mario Bros[61] Problems related to Tetris[62] Verbal arithmetic Other Art gallery problem and its variations. Berth allocation problem[citation needed] Boolean satisfiability problem (SAT).[2][63] There are many variations that are also NP-complete. An important variant is where each clause has exactly three literals (3SAT), since it used in the proof of many other NP-completeness results.[64] Conjunctive Boolean query[65] Cyclic ordering Circuit satisfiability problem Uncapacitated Facility Location Flow Shop Scheduling Problem Generalized assignment problem Upward planarity testing[33] Some problems related to Job-shop scheduling Monochromatic triangle[66] Minimum maximal independent set a.k.a. minimum independent dominating set[67] NP-complete special cases include the minimum maximal matching problem,[68] which is essentially equal to the edge dominating set problem (see above). Maximum common subgraph isomorphism problem[69] Minimum degree spanning tree Minimum k-spanning tree Metric k-center Maximum 2-Satisfiability[70] Modal logic S5-Satisfiability Some problems related to Multiprocessor scheduling Maximum volume submatrix – Problem of selecting the best conditioned subset of a larger m x n matrix. This class of problem is associated with Rank revealing QR factorizations and D optimal experimental design.[71] Minimal addition chains for sequences.[72] The complexity of minimal addition chains for individual numbers is unknown.[73] Non-linear univariate polynomials over GF[2n], n the length of the input. Indeed over any GF[qn]. Open-shop scheduling Pathwidth,[74] or, equivalently, interval thickness, and vertex separation number[75] Pancake sorting distance problem for strings[76] k-Chinese postman Subgraph isomorphism problem[77] Variations of the Steiner tree problem. Specifically, with the discretized Euclidean metric, rectilinear metric. The problem is known to be NP-hard with the (non-discretized) Euclidean metric.[78] Shortest path in general networks Set packing[2][79] Serializability of database histories[80] Scheduling to minimize weighted completion time Sparse approximation Slither Link on a variety of grids[81][82][83][84] Block Sorting (Sorting by Block Moves) Second order instantiation Treewidth[74] Testing whether a tree may be represented as Euclidean minimum spanning tree Three-dimensional Ising model[85] Vehicle routing problem |
About us|Jobs|Help|Disclaimer|Advertising services|Contact us|Sign in|Website map|Search|
GMT+8, 2014-3-16 11:39 , Processed in 0.074857 second(s), 17 queries .
