Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Maximal_independent_set> ?p ?o }
Showing triples 1 to 76 of
76
with 100 triples per page.
- Maximal_independent_set abstract "In graph theory, a maximal independent set (MIS) 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 MIS is also a dominating set in the graph, and every dominating set that is independent must be maximal independent, so MISs are also called independent dominating sets. A graph may have many MISs of widely varying sizes;a largest MISs 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.Two algorithmic problems are associated with MISs: finding a single MIS in a given graph and listing all MISs in a given graph.".
- Maximal_independent_set thumbnail Cube-maximal-independence.svg?width=300.
- Maximal_independent_set wikiPageExternalLink citation.cfm?id=644182.
- Maximal_independent_set wikiPageExternalLink p9qbl6y1v5t3xc1w.
- Maximal_independent_set wikiPageExternalLink Eppstein2003.7.2.pdf.
- Maximal_independent_set wikiPageID "1793590".
- Maximal_independent_set wikiPageLength "28212".
- Maximal_independent_set wikiPageOutDegree "43".
- Maximal_independent_set wikiPageRevisionID "678360319".
- Maximal_independent_set wikiPageWikiLink Algorithm.
- Maximal_independent_set wikiPageWikiLink Algorithmic_problem.
- Maximal_independent_set wikiPageWikiLink Babeş-Bolyai_University.
- Maximal_independent_set wikiPageWikiLink Babeș-Bolyai_University.
- Maximal_independent_set wikiPageWikiLink Bipartite_graph.
- Maximal_independent_set wikiPageWikiLink Category:Computational_problems_in_graph_theory.
- Maximal_independent_set wikiPageWikiLink Category:Graph_theory_objects.
- Maximal_independent_set wikiPageWikiLink Chordal_graph.
- Maximal_independent_set wikiPageWikiLink Clique_problem.
- Maximal_independent_set wikiPageWikiLink Cograph.
- Maximal_independent_set wikiPageWikiLink Complement_(graph_theory).
- Maximal_independent_set wikiPageWikiLink Complement_(set_theory).
- Maximal_independent_set wikiPageWikiLink Complement_graph.
- Maximal_independent_set wikiPageWikiLink Complete_graph.
- Maximal_independent_set wikiPageWikiLink Cycle_graph.
- Maximal_independent_set wikiPageWikiLink Dense_graph.
- Maximal_independent_set wikiPageWikiLink Dominating_set.
- Maximal_independent_set wikiPageWikiLink Glossary_of_graph_theory.
- Maximal_independent_set wikiPageWikiLink Graph_theory.
- Maximal_independent_set wikiPageWikiLink Hard_spheres.
- Maximal_independent_set wikiPageWikiLink Independent_set_(graph_theory).
- Maximal_independent_set wikiPageWikiLink Induced_subgraph.
- Maximal_independent_set wikiPageWikiLink Interval_graph.
- Maximal_independent_set wikiPageWikiLink Journal_of_Graph_Algorithms_and_Applications.
- Maximal_independent_set wikiPageWikiLink Matrix_multiplication.
- Maximal_independent_set wikiPageWikiLink Matroid.
- Maximal_independent_set wikiPageWikiLink Maximum_independent_set.
- Maximal_independent_set wikiPageWikiLink Padovan_sequence.
- Maximal_independent_set wikiPageWikiLink Path_(graph_theory).
- Maximal_independent_set wikiPageWikiLink Perrin_number.
- Maximal_independent_set wikiPageWikiLink Planar_graph.
- Maximal_independent_set wikiPageWikiLink Plastic_number.
- Maximal_independent_set wikiPageWikiLink Sparse_graph.
- Maximal_independent_set wikiPageWikiLink Statistical_mechanics.
- Maximal_independent_set wikiPageWikiLink Theoretical_Computer_Science_(journal).
- Maximal_independent_set wikiPageWikiLink Triangle-free_graph.
- Maximal_independent_set wikiPageWikiLink Turán_graph.
- Maximal_independent_set wikiPageWikiLink Vector_space.
- Maximal_independent_set wikiPageWikiLink Vertex_cover.
- Maximal_independent_set wikiPageWikiLink Vertex_cover_problem.
- Maximal_independent_set wikiPageWikiLink With_high_probability.
- Maximal_independent_set wikiPageWikiLink File:Cube-maximal-independence.svg.
- Maximal_independent_set wikiPageWikiLinkText "Maximal independent set".
- Maximal_independent_set wikiPageWikiLinkText "maximal independent set".
- Maximal_independent_set wikiPageWikiLinkText "maximum independent set".
- Maximal_independent_set hasPhotoCollection Maximal_independent_set.
- Maximal_independent_set wikiPageUsesTemplate Template:About.
- Maximal_independent_set wikiPageUsesTemplate Template:Citation.
- Maximal_independent_set wikiPageUsesTemplate Template:Further.
- Maximal_independent_set wikiPageUsesTemplate Template:Harvtxt.
- Maximal_independent_set wikiPageUsesTemplate Template:Refbegin.
- Maximal_independent_set wikiPageUsesTemplate Template:Refend.
- Maximal_independent_set wikiPageUsesTemplate Template:Reflist.
- Maximal_independent_set subject Category:Computational_problems_in_graph_theory.
- Maximal_independent_set subject Category:Graph_theory_objects.
- Maximal_independent_set type Object.
- Maximal_independent_set comment "In graph theory, a maximal independent set (MIS) 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 MIS is also a dominating set in the graph, and every dominating set that is independent must be maximal independent, so MISs are also called independent dominating sets.".
- Maximal_independent_set label "Maximal independent set".
- Maximal_independent_set sameAs Insieme_indipendente_massimale.
- Maximal_independent_set sameAs m.05xh3m.
- Maximal_independent_set sameAs Наибольшее_независимое_множество.
- Maximal_independent_set sameAs Найбільша_незалежна_множина.
- Maximal_independent_set sameAs Q7888149.
- Maximal_independent_set sameAs Q7888149.
- Maximal_independent_set wasDerivedFrom Maximal_independent_set?oldid=678360319.
- Maximal_independent_set depiction Cube-maximal-independence.svg.
- Maximal_independent_set isPrimaryTopicOf Maximal_independent_set.