Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Maximal_independent_set> ?p ?o. }
Showing items 1 to 29 of
29
with 100 items per page.
- Maximal_independent_set abstract "In graph theory, a maximal independent set or maximal stable set is an independent set that is not a subset of any other independent set. That is, it is a set S such that every edge of the graph has at least one endpoint not in S and every vertex not in S has at least one neighbor in S. A maximal independent set is also a dominating set in the graph, and every dominating set that is independent must be maximal independent, so maximal independent sets are also called independent dominating sets. A graph may have many maximal independent sets of widely varying sizes; a largest maximal independent set is called a maximum independent set.For example, in the graph P3, a path with three vertices a, b, and c, and two edges ab and bc, the sets {b} and {a,c} are both maximally independent. The set {a} is independent, but is not maximal independent, because it is a subset of the larger independent set {a,c}. In this same graph, the maximal cliques are the sets {a,b} and {b,c}.The phrase "maximal independent set" is also used to describe maximal subsets of independent elements in mathematical structures other than graphs, and in particular in vector spaces and matroids.".
- Maximal_independent_set thumbnail Cube-maximal-independence.svg?width=300.
- Maximal_independent_set wikiPageExternalLink citation.cfm?id=644182.
- Maximal_independent_set wikiPageExternalLink Eppstein2003.7.2.pdf.
- Maximal_independent_set wikiPageExternalLink p9qbl6y1v5t3xc1w.
- Maximal_independent_set wikiPageID "1793590".
- Maximal_independent_set wikiPageRevisionID "587868583".
- Maximal_independent_set hasPhotoCollection Maximal_independent_set.
- Maximal_independent_set subject Category:Computational_problems_in_graph_theory.
- Maximal_independent_set subject Category:Graph_theory_objects.
- Maximal_independent_set type Abstraction100002137.
- Maximal_independent_set type Attribute100024264.
- Maximal_independent_set type ComputationalProblemsInGraphTheory.
- Maximal_independent_set type Condition113920835.
- Maximal_independent_set type Difficulty114408086.
- Maximal_independent_set type Problem114410605.
- Maximal_independent_set type State100024720.
- Maximal_independent_set comment "In graph theory, a maximal independent set or maximal stable set is an independent set that is not a subset of any other independent set. That is, it is a set S such that every edge of the graph has at least one endpoint not in S and every vertex not in S has at least one neighbor in S. A maximal independent set is also a dominating set in the graph, and every dominating set that is independent must be maximal independent, so maximal independent sets are also called independent dominating sets.".
- Maximal_independent_set label "Insieme indipendente massimale".
- Maximal_independent_set label "Maximal independent set".
- Maximal_independent_set label "Наибольшее независимое множество".
- Maximal_independent_set sameAs Insieme_indipendente_massimale.
- Maximal_independent_set sameAs m.05xh3m.
- Maximal_independent_set sameAs Q7888149.
- Maximal_independent_set sameAs Q7888149.
- Maximal_independent_set sameAs Maximal_independent_set.
- Maximal_independent_set wasDerivedFrom Maximal_independent_set?oldid=587868583.
- Maximal_independent_set depiction Cube-maximal-independence.svg.
- Maximal_independent_set isPrimaryTopicOf Maximal_independent_set.