Find link

language:

Find link is a tool written by Edward Betts.

searching for Independent set (graph theory) 67 found (161 total)

alternate case: independent set (graph theory)

Tree decomposition (1,531 words) [view diff] no match in snippet view article find links to article

In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain

Complete bipartite graph (959 words) [view diff] no match in snippet view article find links to article

In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first

Expander mixing lemma (2,006 words) [view diff] no match in snippet view article find links to article

185-191. Haemers, W. H. (1979). Eigenvalue Techniques in Design and Graph Theory (PDF) (Ph.D.). Haemers, W. H. (1995), "Interlacing Eigenvalues and Graphs"

Matroid (8,673 words) [view diff] no match in snippet view article find links to article

theory borrows extensively from the terms used in both linear algebra and graph theory, largely because it is the abstraction of various notions of central

Graph property (1,170 words) [view diff] no match in snippet view article find links to article

In graph theory, a graph property or graph invariant is a property of graphs that depends only on the abstract structure, not on graph representations

Hereditary property (1,694 words) [view diff] no match in snippet view article find links to article

context. These properties are particularly considered in topology and graph theory, but also in set theory. In topology, a topological property is said

Multi-trials technique (218 words) [view diff] no match in snippet view article find links to article

Distributed Computing Schneider, J. (2008), "A log-star distributed maximal independent set algorithm for growth-bounded graphs" (PDF), Proceedings of the Symposium

Trivially perfect graph (1,189 words) [view diff] no match in snippet view article find links to article

In graph theory, a trivially perfect graph is a graph with the property that in each of its induced subgraphs the size of the maximum independent set equals

Comparability graph (1,383 words) [view diff] no match in snippet view article find links to article

In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability

Meshulam's game (1,235 words) [view diff] no match in snippet view article find links to article

In graph theory, Meshulam's game is a game used to explain a theorem of Roy Meshulam related to the homological connectivity of the independence complex

Clique problem (9,876 words) [view diff] no match in snippet view article find links to article

model social networks, and adapted the social science terminology to graph theory. They were the first to call complete subgraphs "cliques". The first

Boxicity (1,497 words) [view diff] no match in snippet view article find links to article

In graph theory, boxicity is a graph invariant, introduced by Fred S. Roberts in 1969. The boxicity of a graph is the minimum dimension in which a given

Václav Chvátal (1,468 words) [view diff] no match in snippet view article find links to article

Charles University in Prague. He has published extensively on topics in graph theory, combinatorics, and combinatorial optimization. Chvátal was born in 1946

Connected dominating set (1,222 words) [view diff] no match in snippet view article find links to article

In graph theory, a connected dominating set and a maximum leaf spanning tree are two closely related structures defined on an undirected graph. A connected

Meshulam's game (1,235 words) [view diff] no match in snippet view article find links to article

In graph theory, Meshulam's game is a game used to explain a theorem of Roy Meshulam related to the homological connectivity of the independence complex

Maximum common induced subgraph (721 words) [view diff] no match in snippet view article find links to article

In graph theory and theoretical computer science, a maximum common induced subgraph of two graphs G and H is a graph that is an induced subgraph of both

Penny graph (1,953 words) [view diff] no match in snippet view article find links to article

In geometric graph theory, a penny graph is a contact graph of unit circles. It is formed from a collection of unit circles that do not cross each other

3-dimensional matching (1,558 words) [view diff] no match in snippet view article find links to article

In the mathematical discipline of graph theory, a 3-dimensional matching is a generalization of bipartite matching (also known as 2-dimensional matching)

Cograph (2,701 words) [view diff] no match in snippet view article find links to article

In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation

Circle graph (1,692 words) [view diff] no match in snippet view article find links to article

In graph theory, a circle graph is the intersection graph of a chord diagram. That is, it is an undirected graph whose vertices can be associated with

Three utilities problem (2,748 words) [view diff] no match in snippet view article find links to article

be solved. This puzzle can be formalized as a problem in topological graph theory by asking whether the complete bipartite graph K 3 , 3 {\displaystyle

Acyclic coloring (720 words) [view diff] no match in snippet view article find links to article

In graph theory, an acyclic coloring is a (proper) vertex coloring in which every 2-chromatic subgraph is acyclic. The acyclic chromatic number A(G) of

Richard Rado (516 words) [view diff] no match in snippet view article find links to article

German-born British mathematician whose research concerned combinatorics and graph theory. He was Jewish and left Germany to escape Nazi persecution. He earned

Wagner graph (649 words) [view diff] no match in snippet view article find links to article

In the mathematical field of graph theory, the Wagner graph is a 3-regular graph with 8 vertices and 12 edges. It is the 8-vertex Möbius ladder graph.

Unit disk graph (1,372 words) [view diff] no match in snippet view article find links to article

In geometric graph theory, a unit disk graph is the intersection graph of a family of unit disks in the Euclidean plane. That is, it is a graph with one

Feedback vertex set (1,781 words) [view diff] no match in snippet view article find links to article

In the mathematical discipline of graph theory, a feedback vertex set (FVS) of a graph is a set of vertices whose removal leaves a graph without cycles

Series–parallel graph (1,031 words) [view diff] no match in snippet view article find links to article

In graph theory, series–parallel graphs are graphs with two distinguished vertices called terminals, formed recursively by two simple composition operations

Mac Lane's planarity criterion (1,362 words) [view diff] no match in snippet view article find links to article

In graph theory, Mac Lane's planarity criterion is a characterisation of planar graphs in terms of their cycle spaces, named after Saunders Mac Lane, who

Rank (198 words) [view diff] no match in snippet view article find links to article

position Social status Seniority Rank (differential topology) Rank (graph theory) Rank (linear algebra), the dimension of the vector space generated (or

Even-hole-free graph (714 words) [view diff] no match in snippet view article find links to article

In the mathematical area of graph theory, a graph is even-hole-free if it contains no induced cycle with an even number of vertices. More precisely, the

Frankl–Rödl graph (1,045 words) [view diff] no match in snippet view article find links to article

In graph theory and computational complexity theory, a Frankl–Rödl graph is a graph defined by connecting pairs of vertices of a hypercube that are at

Parity graph (490 words) [view diff] no match in snippet view article find links to article

In graph theory, a parity graph is a graph in which every two induced paths between the same two vertices have the same parity: either both paths have

Cluster graph (647 words) [view diff] no match in snippet view article find links to article

In graph theory, a branch of mathematics, a cluster graph is a graph formed from the disjoint union of complete graphs. Equivalently, a graph is a cluster

Balaban 11-cage (358 words) [view diff] no match in snippet view article find links to article

In the mathematical field of graph theory, the Balaban 11-cage or Balaban (3,11)-cage is a 3-regular graph with 112 vertices and 168 edges named after

Eternal dominating set (1,786 words) [view diff] no match in snippet view article find links to article

In graph theory, an eternal dominating set for a graph G = (V, E) is a subset D of V such that D is a dominating set on which mobile guards are initially

Golomb graph (389 words) [view diff] no match in snippet view article find links to article

In graph theory, the Golomb graph is a polyhedral graph with 10 vertices and 18 edges. It is named after Solomon W. Golomb, who constructed it (with a

Greedoid (1,717 words) [view diff] no match in snippet view article find links to article

Besides mathematical optimization, greedoids have also been connected to graph theory, language theory, order theory, and other areas of mathematics. A set

Bounded expansion (982 words) [view diff] no match in snippet view article find links to article

In graph theory, a family of graphs is said to have bounded expansion if all of its shallow minors are sparse graphs. Many natural families of sparse graphs

Strongly chordal graph (1,167 words) [view diff] no match in snippet view article find links to article

In the mathematical area of graph theory, an undirected graph G is strongly chordal if it is a chordal graph and every cycle of even length (≥ 6) in G

Rainbow matching (2,561 words) [view diff] no match in snippet view article find links to article

In the mathematical discipline of graph theory, a rainbow matching in an edge-colored graph is a matching in which all the edges have distinct colors.

Greedy coloring (3,873 words) [view diff] no match in snippet view article find links to article

theorem on the relation between coloring and degree. Other concepts in graph theory derived from greedy colorings include the Grundy number of a graph (the

Graph removal lemma (4,764 words) [view diff] no match in snippet view article find links to article

In graph theory, the graph removal lemma states that when a graph contains few copies of a given subgraph, then all of the copies can be eliminated by

Paul Seymour (mathematician) (2,272 words) [view diff] no match in snippet view article

mathematician known for his work in discrete mathematics, especially graph theory. He (with others) was responsible for important progress on regular matroids

House allocation problem (1,776 words) [view diff] no match in snippet view article find links to article

maximum allowed envy is just 1. The proof is by reduction from Maximum independent set on cubic graphs. However, the problem is fixed-parameter tractable

Line graph of a hypergraph (1,201 words) [view diff] no match in snippet view article find links to article

In graph theory, particularly in the theory of hypergraphs, the line graph of a hypergraph H, denoted L(H), is the graph whose vertex set is the set of

Distance-hereditary graph (2,290 words) [view diff] no match in snippet view article find links to article

In graph theory, a branch of discrete mathematics, a distance-hereditary graph (also called a completely separable graph) is a graph in which the distances

Halin graph (2,157 words) [view diff] no match in snippet view article find links to article

In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle. The tree must have at least four

Independence system (272 words) [view diff] no match in snippet view article find links to article

ABSTRACT-SIMPLICIAL-COMPLEXES ⊃ MATROIDS. Bondy, Adrian; Murty, U.S.R. (2008), Graph Theory, Graduate Texts in Mathematics, vol. 244, Springer, p. 195, ISBN 9781846289699

Map graph (778 words) [view diff] no match in snippet view article find links to article

In graph theory, a branch of mathematics, a map graph is an undirected graph formed as the intersection graph of finitely many simply connected and internally

List of PSPACE-complete problems (1,806 words) [view diff] no match in snippet view article find links to article

players alternately select vertices and the induced subgraph must be an independent set (resp. clique). The last to play wins. Nondeterministic Constraint

Planar separator theorem (9,917 words) [view diff] no match in snippet view article find links to article

In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into

Hall-type theorems for hypergraphs (6,359 words) [view diff] no match in snippet view article find links to article

In the mathematical field of graph theory, Hall-type theorems for hypergraphs are several generalizations of Hall's marriage theorem from graphs to hypergraphs

Interval edge coloring (1,656 words) [view diff] no match in snippet view article find links to article

In graph theory, interval edge coloring is a type of edge coloring in which edges are labeled by the integers in some interval, every integer in the interval

1-planar graph (2,716 words) [view diff] no match in snippet view article find links to article

In topological graph theory, a 1-planar graph is a graph that can be drawn in the Euclidean plane in such a way that each edge has at most one crossing

List of conjectures by Paul Erdős (1,405 words) [view diff] no match in snippet view article find links to article

Retrieved 2022-06-26. Fan Chung, "Open problems of Paul Erdős in graph theory" Fan Chung, living version of "Open problems of Paul Erdős in graph theory"

Matroid rank (1,429 words) [view diff] no match in snippet view article find links to article

corank to refer to the difference r(E)−r(A){\displaystyle r(E)-r(A)}. In graph theory, the circuit rank (or cyclomatic number) of a graph is the corank of

Pathwidth (7,621 words) [view diff] no match in snippet view article find links to article

In graph theory, a path decomposition of a graph G is, informally, a representation of G as a "thickened" path graph, and the pathwidth of G is a number

Jon Folkman (1,126 words) [view diff] no match in snippet view article find links to article

"geometric lattices" in terms of the free Abelian groups of finite rank. In graph theory, he was the first to study semi-symmetric graphs, and he discovered the

Matroid partitioning (2,031 words) [view diff] no match in snippet view article find links to article

(1997), "5. Fractional arboricity and matroid methods", Fractional graph theory, Wiley-Interscience Series in Discrete Mathematics and Optimization,

Matroid oracle (4,313 words) [view diff] no match in snippet view article find links to article

Cunningham, William H. (1979), "Matroids, graphs, and 3-connectivity", Graph theory and related topics (Proc. Conf., Univ. Waterloo, Waterloo, Ont., 1977)

Mihalis Yannakakis (1,447 words) [view diff] no match in snippet view article find links to article

database theory, computer aided verification and testing, and algorithmic graph theory. Among his contributions to complexity theory are two papers about the

NP-completeness (3,610 words) [view diff] no match in snippet view article find links to article

NP-complete. An interesting example is the graph isomorphism problem, the graph theory problem of determining whether a graph isomorphism exists between two

Matroid parity problem (2,829 words) [view diff] no match in snippet view article find links to article

optimization, the matroid parity problem is a problem of finding the largest independent set of paired elements in a matroid. The problem was formulated by Lawler

Network motif (10,164 words) [view diff] no match in snippet view article find links to article

their functional contribution to the operation of networks. Clique (graph theory) Graphical model Masoudi-Nejad A, Schreiber F, Razaghi MK Z (2012). "Building

Twin-width (3,995 words) [view diff] no match in snippet view article find links to article

"Twin-width and permutations", European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB'23), Masaryk University Press, pp. 156–162

Scale-free network (6,723 words) [view diff] no match in snippet view article find links to article

Heydari, H.; Taheri, S.M.; Kaveh, K. (2018). "Distributed Maximal Independent Set on Scale-Free Networks". arXiv:1804.02513 [cs.DC]. Eom, Young-Ho; Jo

Optimal kidney exchange (1,856 words) [view diff] no match in snippet view article find links to article

to accept as many kidneys as possible. The proofs use concepts from graph theory, such as the Gallai–Edmonds decomposition. It is possible to find a stochastic