About: Independent set (graph theory)

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

Set of vertices in a graph, no two of which are adjacent

Property	Value
dbo:description	Begriff aus der Graphentheorie (de) קבוצת קודקודים שבה אין זוג קודקודים שמחוברים בקשת אחת (iw) egy gráfban olyan csúcsok halmaza, melyek közül semelyik kettő sem szomszédos (hu) set of vertices in a graph, no two of which are adjacent (en) pojęcie teorii grafów (pl) aro de verticoj en grafo tiaj, ke neniun paron el ili konektas eĝo (eo)
dbo:thumbnail	wiki-commons:Special:FilePath/Independent_set_graph.svg?width=300
dbo:wikiPageExternalLink	http://www.hananayad.com/teaching/syde423/IndependentSet.pdf http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm
dbo:wikiPageWikiLink	dbr:Edge_covering dbr:APX dbr:Minor_(graph_theory) dbr:Clique_(graph_theory) dbr:Israel_Journal_of_Mathematics dbr:Computer_science dbr:Synthetic_biology dbr:Gene_regulatory_network dbr:Intersection_graph dbc:Computational_problems_in_graph_theory dbr:Computational_complexity_theory dbr:Graph_theory dbr:Claw-free_graph dbr:Cograph dbr:Modular_decomposition dbr:Journal_of_Graph_Theory dbr:Ramsey_theory dbr:Graph_coloring dbr:Greedy_algorithm dbr:Springer_Science+Business_Media dbr:Earliest_deadline_first_scheduling dbr:Complement_graph dbr:Path_graph dbr:Padovan_sequence dbr:Graph_(discrete_mathematics) dbr:Bipartite_graph dbr:Lecture_Notes_in_Computer_Science dbr:Brute-force_search dbr:Vertex_cover dbr:Optimization_problem dbr:Planar_graph dbr:Approximation_algorithm dbr:Interval_graph dbr:Kőnig's_theorem_(graph_theory) dbr:Algorithmica dbr:Dominating_set dbr:Combinatorica dbr:Matching_(graph_theory) dbr:Perfect_graph dbr:Chordal_graph dbr:Maximal_independent_set dbr:Polynomial-time_approximation_scheme dbr:NP-completeness dbr:Perrin_number dbr:Edge_(graph_theory) dbr:Strong_NP-completeness dbr:Vertex_(graph_theory) dbr:SIAM_Journal_on_Computing dbr:Cycle_graph dbr:Truth_value dbr:Dense_graph dbr:Partition_of_a_set dbr:Automatic_label_placement dbr:Clique_problem dbr:Discrete_&_Computational_Geometry dbr:Information_and_Computation dbr:Journal_of_the_ACM dbr:Polynomial_time dbc:Graph_theory_objects dbc:NP-complete_problems dbr:SNP_(complexity) dbr:Proper_subset dbr:Plastic_number dbr:NP-complete dbr:Springer-Verlag dbr:NP-hard dbr:Theoretical_Computer_Science dbr:Approximation_ratio dbr:Job_scheduling dbr:Computational_problems dbr:Journal_of_Combinatorial_Theory,_Series_B dbr:SODA_(Symposium_on_Discrete_Algorithms) dbr:Vertex_coloring dbr:Clique_separator dbr:File:Independent_set_graph.svg dbr:Journal_of_Operations_Research_Society_Japan
dbp:date	2013-05-29 (xsd:date)
dbp:title	Maximal Independent Vertex Set (en)
dbp:url	https://web.archive.org/web/20130529163947/http:/www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm
dbp:urlname	MaximalIndependentVertexSet (en)
dbp:wikiPageUsesTemplate	dbt:Cite_Geometric_Algorithms_and_Combinatorial_Optimization dbt:Citation dbt:Harvtxt dbt:Main dbt:MathWorld dbt:Refbegin dbt:Refend dbt:Reflist dbt:See dbt:Sfn_whitelist dbt:Short_description dbt:Unsolved dbt:Webarchive dbt:Covering-Packing_Problem_Pairs
dct:subject	dbc:Computational_problems_in_graph_theory dbc:Graph_theory_objects dbc:NP-complete_problems
gold:hypernym	dbr:Set
rdfs:label	Independent set (graph theory) (en) Nezávislá množina (cs) مجموعة مستقلة (نظرية الرسومات) (ar) Stabile Menge (de) Conjunto independiente (es) Stable (théorie des graphes) (fr) Himpunan bebas (teori graf) (in) 独立集合 (ja) 독립집합 (ko) Insieme indipendente (teoria dei grafi) (it) Onafhankelijke verzameling (nl) Conjunto independente (pt) Zbiór niezależny (pl) Oberoende mängd (sv) Независимое множество (ru) 独立集 (zh)
owl:sameAs	freebase:Independent set (graph theory) dbpedia-de:Independent set (graph theory) yago-res:Independent set (graph theory) wikidata:Independent set (graph theory) dbpedia-es:Independent set (graph theory) dbpedia-it:Independent set (graph theory) dbpedia-nl:Independent set (graph theory) dbpedia-pl:Independent set (graph theory) dbpedia-fr:Independent set (graph theory) dbpedia-he:Independent set (graph theory) dbpedia-hu:Independent set (graph theory) dbpedia-ja:Independent set (graph theory) dbpedia-pt:Independent set (graph theory) dbpedia-ru:Independent set (graph theory) dbpedia-zh:Independent set (graph theory) dbpedia-sv:Independent set (graph theory) dbpedia-vi:Independent set (graph theory) dbpedia-id:Independent set (graph theory) dbpedia-ko:Independent set (graph theory) dbpedia-ar:Independent set (graph theory) dbpedia-cs:Independent set (graph theory) dbpedia-fa:Independent set (graph theory) dbpedia-sk:Independent set (graph theory) dbpedia-sr:Independent set (graph theory) dbpedia-th:Independent set (graph theory) dbpedia-global:Independent set (graph theory)
prov:wasDerivedFrom	wikipedia-en:Independent_set_(graph_theory)?oldid=1310200429&ns=0
foaf:depiction	wiki-commons:Special:FilePath/Independent_set_graph.svg
foaf:isPrimaryTopicOf	wikipedia-en:Independent_set_(graph_theory)
is dbo:wikiPageDisambiguates of	dbr:Independent_set
is dbo:wikiPageRedirects of	dbr:Independence_(graph_theory) dbr:Independence_number dbr:Maximum_independent_set dbr:Maximum_independent_set_problem dbr:Anticlique dbr:Approximation_algorithms_for_the_maximum_independent_set_problem dbr:Coclique dbr:Independent_Set_problem dbr:Independent_set_problem dbr:Maximum_independent-set dbr:Vertex_independent_set dbr:Vertex_packing
is dbo:wikiPageWikiLink of	dbr:Search_problem dbr:APX dbr:Holographic_algorithm dbr:Erdős–Ko–Rado_theorem dbr:Girth_(graph_theory) dbr:Moser_spindle dbr:Complete_coloring dbr:Domatic_number dbr:Covering_problems dbr:Fractional_coloring dbr:Point_location dbr:Kayles dbr:Meyniel_graph dbr:Independence_complex dbr:Width_of_a_hypergraph dbr:Method_of_conditional_probabilities dbr:743_(number) dbr:Vizing's_theorem dbr:Union-closed_sets_conjecture dbr:Clique_(graph_theory) dbr:Trapezoid_graph dbr:Triangle-free_graph dbr:Induced_matching dbr:Baker's_technique dbr:Coxeter_graph dbr:Expander_graph dbr:Fibonacci_cube dbr:Odd_graph dbr:288_(number) dbr:Clique_cover dbr:Dually_chordal_graph dbr:Grundy_number dbr:Incidence_coloring dbr:Nondeterministic_constraint_logic dbr:Extremal_graph_theory dbr:Graph_theory dbr:Turán's_theorem dbr:Claw-free_graph dbr:Cocoloring dbr:Longest_increasing_subsequence dbr:Set_packing dbr:Ermelinda_DeLaViña dbr:Universal_vertex dbr:Probabilistic_method dbr:Andrew_M._Gleason dbr:Clebsch_graph dbr:Graph_coloring dbr:Greedy_algorithm dbr:Complement_graph dbr:Ramsey's_theorem dbr:Book_embedding dbr:Lovász_number dbr:Induced_subgraph dbr:Parameterized_complexity dbr:Iterative_compression dbr:Bipartite_graph dbr:Threshold_graph dbr:Glossary_of_graph_theory dbr:Bull_graph dbr:Higman–Sims_graph dbr:M22_graph dbr:Apollonian_network dbr:Exact_coloring dbr:Hadwiger_number dbr:Hajós_construction dbr:Courcelle's_theorem dbr:Vertex_cover dbr:Tree_contraction dbr:Transversal_(combinatorics) dbr:Certificate_(complexity) dbr:Linear_programming dbr:Approximation_algorithm dbr:Interval_graph dbr:Kőnig's_theorem_(graph_theory) dbr:Dilworth's_theorem dbr:Neighbourhood_(graph_theory) dbr:Perfect_graph_theorem dbr:Dominating_set dbr:Bidimensionality dbr:Split_graph dbr:Dulmage–Mendelsohn_decomposition dbr:Birkhoff's_representation_theorem dbr:Rainbow-independent_set dbr:227_(number) dbr:PLS_(complexity) dbr:Packing_in_a_hypergraph dbr:Maximal_independent_set dbr:Uniquely_colorable_graph dbr:Well-covered_graph dbr:Induced_path dbr:Spectral_graph_theory dbr:Quasi-bipartite_graph dbr:Linkless_embedding dbr:Intersection_number_(graph_theory) dbr:Interval_scheduling dbr:Maximum_disjoint_set dbr:Path_cover dbr:Shannon_capacity_of_a_graph dbr:Skew-merged_permutation dbr:Quantum_contextuality dbr:Binary_logarithm dbr:Vertex_(graph_theory) dbr:Defective_coloring dbr:Computational_problem dbr:Eight_queens_puzzle dbr:Hoffman–Singleton_graph dbr:Permutation_graph dbr:Chromatic_polynomial dbr:2-satisfiability dbr:Abstract_simplicial_complex dbr:Rook's_graph dbr:Strong_coloring dbr:Queen's_graph dbr:Splittance dbr:List_of_graph_theory_topics dbr:Cubic_graph dbr:Line_graph dbr:Multipartite_graph dbr:Independent_set dbr:Induced_subgraph_isomorphism_problem dbr:Metric_k-center dbr:Graph_entropy dbr:Pseudorandom_graph dbr:Container_method dbr:Flag_algebra dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Enumeration_algorithm dbr:Stable_set dbr:Ramsey-Turán_theory dbr:Independence_(graph_theory) dbr:Deficiency_(graph_theory) dbr:Separation_oracle dbr:Erdős–Hajnal_conjecture dbr:Randomized_rounding dbr:Rectangle_packing dbr:Erdős–Dushnik–Miller_theorem dbr:Independence_number dbr:Maximum_independent_set dbr:Maximum_independent_set_problem dbr:Word-representable_graph dbr:Anticlique dbr:Approximation_algorithms_for_the_maximum_independent_set_problem dbr:Coclique dbr:Independent_Set_problem dbr:Independent_set_problem dbr:Maximum_independent-set dbr:Vertex_independent_set dbr:Vertex_packing
is foaf:primaryTopic of	wikipedia-en:Independent_set_(graph_theory)