| Webster's Online Dictionary |
| Expressions | Definition | ||
| Independent set | In graph theory, an independent, or stable, set in a graph G, which contains vertices V, is a set of vertices V' (a subset of V) such that for every two vertices in V', there is no edge connecting the two. In other words, each edge in the graph is incident to at most one vertex in the set. The size of an independent set is the number of vertices it contains. (references) | ||
| Independent set problem | In mathematics, the independent set problem (IS) is a question in graph theory and combinatorics, known to be an NP-complete problem. (references) | ||
| Maximal independent set | A maximal independent set is an independent set such that adding any other node to the set makes the set no longer independent. (references) | ||
Source: compiled by the editor from various references; see credits. | Top | ||
| Expressions | Domain | Definition | |
| Maximal independent set | Math | A set of vertices in a graph such that for any pair of vertices, there is no edge between them and such that no more vertices can be added and it still be an independent set. (references) | |
Source: compiled by the editor from various references; see credits. | Top | ||
