Independent set (graph theory) (original) (raw)

About DBpedia

Nezávislá množina (NM) je pojem z teorie grafů. Nezávislá množina v grafu je taková množina jeho vrcholů, že žádné dva z nich nejsou spojeny hranou.

thumbnail

Property Value
dbo:abstract في نظرية الرسم البياني، نعرف مجموعة مستقلة أومجموعة مستقرة (stable set أو independent set) بأنها مجموعة من رؤوس والتي كل رأسين بها هما غير متجاوران. بمعنى آخر، المجموعة المستقلة هي مجموعة S من الرؤوس بحيث لا يوجد ضلع يربط بين كل رأسين في S. وهذا يعني أن كل ضلع في الرسم البياني له رأس واحد عالأكثر واحدة على الأكثر في S. حجم المجموعة المستقلة هو عدد الرؤوس بها. تسمى المجموعات المستقلة أيضا بمجموعات مستقرة داخليا. المجموعة المستقلة القصوى (maximal independent set ) هي إما مجموعة مستقلة بحيث أن إضافة أي رأس لها ينتج عنه ضلع ينتمي بالكامل لهذه المجموعة أو مجموعة من جميع رؤوس الرسم البياني الخالي (أي لايحتوي على أضلاع). تعرف المجموعة المستقلة القصوى بشكل آخر بأنها مجموعة مستقلة والتي لها أكبر حجم ممكن للرسم البياني G المحدد. يُسمى هذا الرقم بعدد الاستقلال (independence) لـ G ، ويرمز بالرمز . تعتبر مسألة إيجاد المجموعة المستقلة القصوى مشكلة من النوع NP-hard بمسائل الأمثلية. فبالتالي فإنه من غير المحتمل وجود خوارزمية فعالة لإيجاد الحد الأقصى المستقل لمجموعة من الرسم البياني. كل مجموعة مستقلة قصوى هي أيضًا الحد الأقصى، لكن العكس ليس دائما صحيح. (ar) Nezávislá množina (NM) je pojem z teorie grafů. Nezávislá množina v grafu je taková množina jeho vrcholů, že žádné dva z nich nejsou spojeny hranou. (cs) Eine stabile Menge, unabhängige Menge oder Co-Clique ist in der Graphentheorie eine Teilmenge von Knoten eines Graphen, die zueinander nicht adjazent sind. Zu entscheiden, ob ein Graph eine stabile Menge einer bestimmten Mindestgröße enthält, wird Stabilitätsproblem genannt und gilt, wie das Finden einer größten stabilen Menge, als algorithmisch schwierig. (de) En teoría de grafos, un conjunto independiente o estable es un conjunto de vértices en un grafo tal que ninguno de sus vértices es adyacente a otro. Es decir, es un conjunto V de vértices tal que para ningún par de ellos existe alguna arista que los conecten. En otras palabras, cada arista en el grafo contiene a lo más un vértice en V. El tamaño de un conjunto independiente es el número de vértices que contiene. Un ​ es un conjunto independiente tal que añadiendo cualquier otro vértice al conjunto, este deja de ser independiente. (es) In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set of vertices such that for every two vertices in , there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in . A set is independent if and only if it is a clique in the graph's complement. The size of an independent set is the number of vertices it contains. Independent sets have also been called "internally stable sets", of which "stable set" is a shortening. A maximal independent set is an independent set that is not a proper subset of any other independent set. A maximum independent set is an independent set of largest possible size for a given graph . This size is called the independence number of and is usually denoted by . The optimization problem of finding such a set is called the maximum independent set problem. It is a strongly NP-hard problem. As such, it is unlikely that there exists an efficient algorithm for finding a maximum independent set of a graph. Every maximum independent set also is maximal, but the converse implication does not necessarily hold. (en) Dalam teori graf, himpunan bebas (bahasa Inggris: independent set) adalah serangkaian simpul (vertex) dalam graf, tidak ada dua yang berdekatan. Artinya, ada himpunan I dari simpul tersebut di mana untuk setiap dua simpul dalam I, tidak ada tepi yang menghubungkan keduanya. Hal ini Ekuivalen dengan pernyataan bahwa masing-masing sisi (edge) dalam grafik memiliki paling banyak satu titik akhir di I. (in) En théorie des graphes, un stable – appelé aussi ensemble indépendant ou independent set en anglais – est un ensemble de sommets deux à deux non adjacents. La taille d'un stable est égale au nombre de sommets qu'il contient. (fr) グラフ理論における独立集合(どくりつしゅうごう、英: independent set)または安定集合(英: stable set)は、1つのグラフ内で互いに隣接していない頂点の集合である。すなわち、頂点の集合 V で、V の任意の2つの頂点をつなぐ辺が存在しない場合をいう。等価的に、そのグラフの各辺の高々一方の端点のみが V の元である。独立集合の大きさとはその中の頂点の個数である。 (maximal independent set) とは、任意の他の頂点を追加するとその集合に辺の両端点が含まれてしまうような独立集合である。 最大独立集合 (maximum independent set) は与えられたグラフ G の最も大きな独立集合であり、その大きさを α(G) と表記する。このような集合を求める問題を最大独立集合問題と呼び、NP完全問題である。したがって、グラフの最大独立集合を求める効率的なアルゴリズムは存在が疑わしい。 与えられたグラフが特定の大きさの独立集合を持つかどうかを判定する問題を独立集合問題と呼ぶ。これは計算上、そのグラフが特定の大きさのクリークを持つかどうかの判定と等価である。このことは、グラフが大きさ k の独立集合を持つとき、その補グラフ(頂点は同じだが、辺が相補的なグラフ)は大きさ k のクリークを持つという事実から導かれる。独立集合(およびクリーク)の決定問題は、NP完全問題であることが知られている。 最大独立集合と極大独立集合は異なる概念である。極大独立集合は他のもっと大きな独立集合の部分集合とはならない。極大独立集合を求める問題は簡単な貪欲法で多項式時間で解くことができる。 (ja) 그래프 이론에서 독립 집합(獨立集合, 영어: independent set)은 서로 인접하지 않는 꼭짓점들의 집합이다. (ko) Nella teoria dei grafi, un insieme indipendente o insieme stabile è un insieme di vertici in un grafo, nessuno dei quali è adiacente a due a due. Cioè, è un insieme I di vertici tale che per ogni due vertici in I, non c'è nessuno spigolo che connette i due. Equivalentemente, ciascuno spigolo del grafo ha al massimo un estremo in I. La dimensione di un insieme indipendente è il numero di vertici che esso contiene. Gli insiemi indipendenti sono stati chiamati anche insiemi internamente stabili. Un insieme indipendente massimale è un insieme indipendente tale che aggiungere un qualsiasi vertice all'insieme costringe l'insieme stesso a contenere uno spigolo. Un insieme indipendente massimo è un insieme indipendente della più grande dimensione possibile per un dato grafo G. Questa dimensione è chiamata numero d'indipendenza di G, e denotata α(G). Il problema di trovare un tale insieme è chiamato problema del massimo insieme indipendente ed è un problema di ottimizzazione NP-difficile. Come tale, è improbabile che esista un algoritmo efficiente per trovare un insieme indipendente massimo di un grafo. Ogni massimo insieme indipendente è anche massimale, ma l'implicazione inversa non è necessariamente valida. (it) In de grafentheorie verstaat men onder onafhankelijke verzameling of stabiele verzameling (independent set in het Engels) van een graaf, een deelverzameling van de knopen van die graaf die twee aan twee niet verbonden zijn door een zijde. (nl) Na teoria dos grafos, um conjunto independente de um grafo é um conjunto de vértices de tal que não existem dois vértices adjacentes contidos em S. Em outras palavras, se e são vértices quaisquer de um conjunto independente, não há aresta entre e . Todo grafo tem ao menos um conjunto independente: o conjunto vazio. Um grafo pode ter vários conjuntos independentes distintos. Se S é um conjunto independente de G e não existe um conjunto independente de G maior que S, diz-se que S é um conjunto independente máximo de G. O problema de, dado um grafo G, determinar se há um conjunto independente de tamanho k é um problema NP-completo. (pt) Zbiór niezależny w grafie – zbiór wierzchołków pomiędzy którymi nie ma żadnej krawędzi. Innymi słowy każda krawędź w jest incydentna z co najwyżej jednym wierzchołkiem w tym zbiorze. Problem największego zbioru niezależnego polegający na znalezieniu w danym grafie zbioru niezależnego o maksymalnej liczbie wierzchołków, jest znanym problemem NP-trudnym. Problem ten nie powinien być mylony z maksymalnym zbiorem niezależnym w sensie inkluzji. Zbiór taki jest maksymalny gdy dodanie do niego jakiegokolwiek elementu sprawia że przestaje być niezależny. Znalezienie takiego zbioru wierzchołków jest proste i może być wykonane za pomocą algorytmu zachłannego. * 9 zaznaczonych na niebiesko wierzchołków tworzy (zaskakująco asymetryczny) maksymalny zbiór niezależny w tym grafie o 24 wierzchołkach. (pl) En oberoende mängd är inom matematik, specifikt grafteori, en mängd av noder M i en graf G sådan att det inte finns någon båge i G mellan någon av noderna i M. Ekvivalent uttryckt så är mängden M oberoende om varje båge i G har högst en ändpunkt som ligger i M. Med storleken på en oberoende mängd avses antalet noder som mängden innehåller. En maximal oberoende mängd är en oberoende mängd sådan att om man lägger till en nod i mängden är den inte oberoende längre. En största oberoende mängd är en oberoende mängd sådan att det inte finns någon oberoende mängd som har fler noder. Storleken på en största oberoende mängd kallas grafens oberoendetal. Även när det gäller bågar i grafer talas det om oberoende mängder, dessa kallas vanligtvis matchningar. (sv) Независимое множество в теории графов может быть как независимым множеством вершин, так и независимым множеством рёбер. Независимые множества рассматриваются в задачах покрытия графов. (ru) 独立集(英语:Independent set)是图论中的概念。一个独立集(也称为稳定集)是一个图中一些两两不相邻的顶点所形成的集合。换句话说,独立集由图中若干顶点组成,且中任两个顶点之间没有边。等价地,图中的每条边至多有一个端点属于。一个独立集的基数是它包含顶点的数目。 如果往图的独立集中添加任一个顶点都会使独立性丧失(亦即造成某两点间有边),那么称是极大独立集。如果是图中所有独立集之中基数最大的,那么称是最大独立集,且将该基数称为的独立数,记为。一般来讲,图中可能存在多个极大独立集;最大独立集亦如是。最大独立集一定是极大独立集,但反之未必。 给定一张图,寻找其中一个最大独立集的问题被称为最大独立集问题。该问题已知是NP困难的最优化问题,且即便试图以常数倍近似也是NP困难的。因此,计算机科学家普遍相信不存在解决该问题的高效算法,无论是精确求解还是以常数倍近似求解。 (zh)
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:wikiPageID 524501 (xsd:integer)
dbo:wikiPageLength 24863 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID 1082877025 (xsd:integer)
dbo:wikiPageWikiLink dbr:Proper_subset dbr:Minor_(graph_theory) dbr:Strong_NP-completeness dbr:SODA_(Symposium_on_Discrete_Algorithms) dbr:Dense_graph dbr:Algorithmica dbr:Approximation_algorithm dbr:Path_graph dbr:Vertex_cover dbr:Earliest_deadline_first_scheduling dbr:Information_and_Computation dbr:Kőnig's_theorem_(graph_theory) dbc:Graph_theory_objects dbc:NP-complete_problems dbr:Matching_(graph_theory) dbr:Maximal_independent_set dbr:Gene_regulatory_network dbr:Clique_problem dbr:Graph_(discrete_mathematics) dbr:Graph_coloring dbr:NP-complete dbr:NP-hard dbr:SIAM_Journal_on_Computing dbr:Claw-free_graph dbr:Clique_(graph_theory) dbr:Combinatorica dbr:Complement_graph dbr:Computational_complexity_theory dbr:Computer_science dbr:Padovan_sequence dbr:Perfect_graph dbr:Perrin_number dbr:Synthetic_biology dbr:Truth_value dbr:Lecture_Notes_in_Computer_Science dbr:Cycle_graph dbr:Edge_(graph_theory) dbr:Partition_of_a_set dbr:Discrete_&_Computational_Geometry dbr:Graph_theory dbr:Israel_Journal_of_Mathematics dbr:Journal_of_Graph_Theory dbr:Journal_of_the_ACM dbr:Ramsey_theory dbr:Intersection_graph dbr:Interval_graph dbr:APX dbr:Chordal_graph dbr:Bipartite_graph dbc:Computational_problems_in_graph_theory dbr:Cograph dbr:Modular_decomposition dbr:Dominating_set dbr:Automatic_label_placement dbr:Planar_graph dbr:Plastic_number dbr:Polynomial-time_approximation_scheme dbr:Springer_Science+Business_Media dbr:Greedy_algorithm dbr:Polynomial_time dbr:Approximation_ratio dbr:Theoretical_Computer_Science dbr:Brute-force_search dbr:Optimization_problem dbr:SNP_(complexity) dbr:Vertex_(graph_theory) dbr:Computational_problems dbr:NP-completeness dbr:Job_scheduling dbr:Springer-Verlag dbr:Edge_covering dbr:Vertex_coloring dbr:Journal_of_Combinatorial_Theory,_Series_B dbr:Clique_separator dbr:File:Independent_set_graph.svg dbr:Journal_of_Operations_Research_Society_Japan
dbp:title Maximal Independent Vertex Set (en)
dbp:urlname MaximalIndependentVertexSet (en)
dbp:wikiPageUsesTemplate dbt:Citation dbt:Harvtxt dbt:Main dbt:MathWorld dbt:Refbegin dbt:Refend dbt:Reflist dbt:See dbt:Short_description dbt:Covering-Packing_Problem_Pairs
dcterms:subject dbc:Graph_theory_objects dbc:NP-complete_problems dbc:Computational_problems_in_graph_theory
gold:hypernym dbr:Set
rdf:type yago:WikicatComputationalProblemsInGraphTheory yago:WikicatNP-completeProblems yago:Abstraction100002137 yago:Attribute100024264 yago:Cognition100023271 yago:Concept105835747 yago:Condition113920835 yago:Content105809192 yago:Difficulty114408086 yago:Feature105849789 yago:Idea105833840 yago:Invariant105850432 yago:Problem114410605 yago:Property105849040 yago:PsychologicalFeature100023100 yago:WikicatGraphInvariants yago:State100024720
rdfs:comment Nezávislá množina (NM) je pojem z teorie grafů. Nezávislá množina v grafu je taková množina jeho vrcholů, že žádné dva z nich nejsou spojeny hranou. (cs) Eine stabile Menge, unabhängige Menge oder Co-Clique ist in der Graphentheorie eine Teilmenge von Knoten eines Graphen, die zueinander nicht adjazent sind. Zu entscheiden, ob ein Graph eine stabile Menge einer bestimmten Mindestgröße enthält, wird Stabilitätsproblem genannt und gilt, wie das Finden einer größten stabilen Menge, als algorithmisch schwierig. (de) En teoría de grafos, un conjunto independiente o estable es un conjunto de vértices en un grafo tal que ninguno de sus vértices es adyacente a otro. Es decir, es un conjunto V de vértices tal que para ningún par de ellos existe alguna arista que los conecten. En otras palabras, cada arista en el grafo contiene a lo más un vértice en V. El tamaño de un conjunto independiente es el número de vértices que contiene. Un ​ es un conjunto independiente tal que añadiendo cualquier otro vértice al conjunto, este deja de ser independiente. (es) Dalam teori graf, himpunan bebas (bahasa Inggris: independent set) adalah serangkaian simpul (vertex) dalam graf, tidak ada dua yang berdekatan. Artinya, ada himpunan I dari simpul tersebut di mana untuk setiap dua simpul dalam I, tidak ada tepi yang menghubungkan keduanya. Hal ini Ekuivalen dengan pernyataan bahwa masing-masing sisi (edge) dalam grafik memiliki paling banyak satu titik akhir di I. (in) En théorie des graphes, un stable – appelé aussi ensemble indépendant ou independent set en anglais – est un ensemble de sommets deux à deux non adjacents. La taille d'un stable est égale au nombre de sommets qu'il contient. (fr) 그래프 이론에서 독립 집합(獨立集合, 영어: independent set)은 서로 인접하지 않는 꼭짓점들의 집합이다. (ko) In de grafentheorie verstaat men onder onafhankelijke verzameling of stabiele verzameling (independent set in het Engels) van een graaf, een deelverzameling van de knopen van die graaf die twee aan twee niet verbonden zijn door een zijde. (nl) Независимое множество в теории графов может быть как независимым множеством вершин, так и независимым множеством рёбер. Независимые множества рассматриваются в задачах покрытия графов. (ru) 独立集(英语:Independent set)是图论中的概念。一个独立集(也称为稳定集)是一个图中一些两两不相邻的顶点所形成的集合。换句话说,独立集由图中若干顶点组成,且中任两个顶点之间没有边。等价地,图中的每条边至多有一个端点属于。一个独立集的基数是它包含顶点的数目。 如果往图的独立集中添加任一个顶点都会使独立性丧失(亦即造成某两点间有边),那么称是极大独立集。如果是图中所有独立集之中基数最大的,那么称是最大独立集,且将该基数称为的独立数,记为。一般来讲,图中可能存在多个极大独立集;最大独立集亦如是。最大独立集一定是极大独立集,但反之未必。 给定一张图,寻找其中一个最大独立集的问题被称为最大独立集问题。该问题已知是NP困难的最优化问题,且即便试图以常数倍近似也是NP困难的。因此,计算机科学家普遍相信不存在解决该问题的高效算法,无论是精确求解还是以常数倍近似求解。 (zh) في نظرية الرسم البياني، نعرف مجموعة مستقلة أومجموعة مستقرة (stable set أو independent set) بأنها مجموعة من رؤوس والتي كل رأسين بها هما غير متجاوران. بمعنى آخر، المجموعة المستقلة هي مجموعة S من الرؤوس بحيث لا يوجد ضلع يربط بين كل رأسين في S. وهذا يعني أن كل ضلع في الرسم البياني له رأس واحد عالأكثر واحدة على الأكثر في S. حجم المجموعة المستقلة هو عدد الرؤوس بها. تسمى المجموعات المستقلة أيضا بمجموعات مستقرة داخليا. كل مجموعة مستقلة قصوى هي أيضًا الحد الأقصى، لكن العكس ليس دائما صحيح. (ar) In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set of vertices such that for every two vertices in , there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in . A set is independent if and only if it is a clique in the graph's complement. The size of an independent set is the number of vertices it contains. Independent sets have also been called "internally stable sets", of which "stable set" is a shortening. (en) Nella teoria dei grafi, un insieme indipendente o insieme stabile è un insieme di vertici in un grafo, nessuno dei quali è adiacente a due a due. Cioè, è un insieme I di vertici tale che per ogni due vertici in I, non c'è nessuno spigolo che connette i due. Equivalentemente, ciascuno spigolo del grafo ha al massimo un estremo in I. La dimensione di un insieme indipendente è il numero di vertici che esso contiene. Gli insiemi indipendenti sono stati chiamati anche insiemi internamente stabili. (it) グラフ理論における独立集合(どくりつしゅうごう、英: independent set)または安定集合(英: stable set)は、1つのグラフ内で互いに隣接していない頂点の集合である。すなわち、頂点の集合 V で、V の任意の2つの頂点をつなぐ辺が存在しない場合をいう。等価的に、そのグラフの各辺の高々一方の端点のみが V の元である。独立集合の大きさとはその中の頂点の個数である。 (maximal independent set) とは、任意の他の頂点を追加するとその集合に辺の両端点が含まれてしまうような独立集合である。 最大独立集合 (maximum independent set) は与えられたグラフ G の最も大きな独立集合であり、その大きさを α(G) と表記する。このような集合を求める問題を最大独立集合問題と呼び、NP完全問題である。したがって、グラフの最大独立集合を求める効率的なアルゴリズムは存在が疑わしい。 最大独立集合と極大独立集合は異なる概念である。極大独立集合は他のもっと大きな独立集合の部分集合とはならない。極大独立集合を求める問題は簡単な貪欲法で多項式時間で解くことができる。 (ja) Zbiór niezależny w grafie – zbiór wierzchołków pomiędzy którymi nie ma żadnej krawędzi. Innymi słowy każda krawędź w jest incydentna z co najwyżej jednym wierzchołkiem w tym zbiorze. Problem największego zbioru niezależnego polegający na znalezieniu w danym grafie zbioru niezależnego o maksymalnej liczbie wierzchołków, jest znanym problemem NP-trudnym. * 9 zaznaczonych na niebiesko wierzchołków tworzy (zaskakująco asymetryczny) maksymalny zbiór niezależny w tym grafie o 24 wierzchołkach. (pl) Na teoria dos grafos, um conjunto independente de um grafo é um conjunto de vértices de tal que não existem dois vértices adjacentes contidos em S. Em outras palavras, se e são vértices quaisquer de um conjunto independente, não há aresta entre e . Todo grafo tem ao menos um conjunto independente: o conjunto vazio. Um grafo pode ter vários conjuntos independentes distintos. (pt) En oberoende mängd är inom matematik, specifikt grafteori, en mängd av noder M i en graf G sådan att det inte finns någon båge i G mellan någon av noderna i M. Ekvivalent uttryckt så är mängden M oberoende om varje båge i G har högst en ändpunkt som ligger i M. Med storleken på en oberoende mängd avses antalet noder som mängden innehåller. Även när det gäller bågar i grafer talas det om oberoende mängder, dessa kallas vanligtvis matchningar. (sv)
rdfs:label مجموعة مستقلة (نظرية الرسومات) (ar) Nezávislá množina (cs) Stabile Menge (de) Conjunto independiente (es) Himpunan bebas (teori graf) (in) Stable (théorie des graphes) (fr) Independent set (graph theory) (en) Insieme indipendente (teoria dei grafi) (it) 독립집합 (ko) 独立集合 (ja) Onafhankelijke verzameling (nl) Zbiór niezależny (pl) Conjunto independente (pt) Независимое множество (ru) Oberoende mängd (sv) 独立集 (zh)
owl:sameAs dbpedia-de:Independent set (graph theory) freebase:Independent set (graph theory) yago-res:Independent set (graph theory) wikidata:Independent set (graph theory) dbpedia-ar:Independent set (graph theory) dbpedia-cs:Independent set (graph theory) dbpedia-es:Independent set (graph theory) dbpedia-fa:Independent set (graph theory) dbpedia-fr:Independent set (graph theory) dbpedia-he:Independent set (graph theory) dbpedia-hu:Independent set (graph theory) dbpedia-id:Independent set (graph theory) dbpedia-it:Independent set (graph theory) dbpedia-ja:Independent set (graph theory) dbpedia-ko:Independent set (graph theory) dbpedia-nl:Independent set (graph theory) dbpedia-pl:Independent set (graph theory) dbpedia-pt:Independent set (graph theory) dbpedia-ru:Independent set (graph theory) dbpedia-sk:Independent set (graph theory) dbpedia-sr:Independent set (graph theory) dbpedia-sv:Independent set (graph theory) dbpedia-th:Independent set (graph theory) dbpedia-vi:Independent set (graph theory) dbpedia-zh:Independent set (graph theory) https://global.dbpedia.org/id/8ong
prov:wasDerivedFrom wikipedia-en:Independent_set_(graph_theory)?oldid=1082877025&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_number dbr:Approximation_algorithms_for_the_maximum_independent_set_problem dbr:Coclique dbr:Maximum_independent-set dbr:Independent_Set_problem dbr:Independent_set_problem dbr:Anticlique dbr:Independence_(graph_theory) dbr:Maximum_independent_set dbr:Maximum_independent_set_problem dbr:Vertex_independent_set dbr:Vertex_packing
is dbo:wikiPageWikiLink of dbr:Probabilistic_method dbr:Queen's_graph dbr:Rook's_graph dbr:Enumeration_algorithm dbr:Moser_spindle dbr:M22_graph dbr:Method_of_conditional_probabilities dbr:Metric_k-center dbr:Quantum_contextuality dbr:Binary_logarithm dbr:Book_embedding dbr:Apollonian_network dbr:Approximation_algorithm dbr:List_of_graph_theory_topics dbr:Cubic_graph dbr:Vertex_cover dbr:Vizing's_theorem dbr:Defective_coloring dbr:Deficiency_(graph_theory) dbr:Dulmage–Mendelsohn_decomposition dbr:Incidence_coloring dbr:Independence_complex dbr:Independence_number dbr:Induced_matching dbr:Induced_path dbr:Induced_subgraph dbr:Induced_subgraph_isomorphism_problem dbr:Intersection_number_(graph_theory) dbr:Interval_scheduling dbr:Kőnig's_theorem_(graph_theory) dbr:Pseudorandom_graph dbr:Complete_coloring dbr:Maximal_independent_set dbr:Maximum_disjoint_set dbr:Neighbourhood_(graph_theory) dbr:Union-closed_sets_conjecture dbr:Chromatic_polynomial dbr:Girth_(graph_theory) dbr:Glossary_of_graph_theory dbr:Graph_coloring dbr:Multipartite_graph dbr:Container_method dbr:Erdős–Dushnik–Miller_theorem dbr:Erdős–Hajnal_conjecture dbr:Ermelinda_DeLaViña dbr:Andrew_M._Gleason dbr:Approximation_algorithms_for_the_maximum_independent_set_problem dbr:Line_graph dbr:Linkless_embedding dbr:Lovász_number dbr:Claw-free_graph dbr:Clebsch_graph dbr:Clique_(graph_theory) dbr:Clique_cover dbr:Complement_graph dbr:Computational_problem dbr:PLS_(complexity) dbr:Meyniel_graph dbr:Shannon_capacity_of_a_graph dbr:743_(number) dbr:Triangle-free_graph dbr:Well-covered_graph dbr:Domatic_number dbr:Dually_chordal_graph dbr:Coclique dbr:Linear_programming dbr:Spectral_graph_theory dbr:Path_cover dbr:Trapezoid_graph dbr:Abstract_simplicial_complex dbr:227_(number) dbr:288_(number) dbr:Erdős–Ko–Rado_theorem dbr:Expander_graph dbr:Dilworth's_theorem dbr:Fractional_coloring dbr:Graph_entropy dbr:Graph_theory dbr:Iterative_compression dbr:Kayles dbr:2-satisfiability dbr:Hadwiger_number dbr:Hajós_construction dbr:Interval_graph dbr:Baker's_technique dbr:Courcelle's_theorem dbr:Covering_problems dbr:Coxeter_graph dbr:Uniquely_colorable_graph dbr:APX dbr:Bidimensionality dbr:Bipartite_graph dbr:Birkhoff's_representation_theorem dbr:Cocoloring dbr:Eight_queens_puzzle dbr:Higman–Sims_graph dbr:Hoffman–Singleton_graph dbr:Holographic_algorithm dbr:Threshold_graph dbr:Transversal_(combinatorics) dbr:Width_of_a_hypergraph dbr:Rectangle_packing dbr:Stable_set dbr:Dominating_set dbr:Bull_graph dbr:Split_graph dbr:Splittance dbr:Fibonacci_cube dbr:Greedy_algorithm dbr:Grundy_number dbr:Maximum_independent-set dbr:Independent_Set_problem dbr:Independent_set_problem dbr:Anticlique dbr:Odd_graph dbr:Rainbow-independent_set dbr:Ramsey's_theorem dbr:Certificate_(complexity) dbr:Search_problem dbr:Independence_(graph_theory) dbr:Independent_set dbr:Longest_increasing_subsequence dbr:Vertex_(graph_theory) dbr:Extremal_graph_theory dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Turán's_theorem dbr:Point_location dbr:Exact_coloring dbr:Flag_algebra dbr:Strong_coloring dbr:Universal_vertex dbr:Separation_oracle dbr:Nondeterministic_constraint_logic dbr:Packing_in_a_hypergraph dbr:Perfect_graph_theorem dbr:Permutation_graph dbr:Ramsey-Turán_theory dbr:Set_packing dbr:Parameterized_complexity dbr:Quasi-bipartite_graph dbr:Skew-merged_permutation dbr:Randomized_rounding dbr:Tree_contraction dbr:Maximum_independent_set dbr:Word-representable_graph dbr:Maximum_independent_set_problem dbr:Vertex_independent_set dbr:Vertex_packing
is foaf:primaryTopic of wikipedia-en:Independent_set_(graph_theory)