Faster access than browser!
62 relations: Algorithmica, Approximation algorithm, APX, Automatic label placement, Bipartite graph, Brute-force search, BSD licenses, Chordal graph, Claw-free graph, Clique (graph theory), Clique problem, Cograph, Combinatorica, Complement graph, Computational problem, Computer science, Cycle graph, Dense graph, Dominating set, Earliest deadline first scheduling, Edge cover, Glossary of graph theory terms, GNU General Public License, Graph (discrete mathematics), Graph coloring, Graph minor, Graph theory, Greedy algorithm, Information and Computation, Intersection graph, Interval graph, Job scheduler, Journal of Combinatorial Theory, Journal of the ACM, Kőnig's theorem (graph theory), Lecture Notes in Computer Science, Matching (graph theory), Maximal independent set, Modular decomposition, NetworkX, NP-completeness, NP-hardness, Optimization problem, Padovan sequence, Partition of a set, Path graph, Perfect graph, Perrin number, Planar graph, Plastic number, ..., Polynomial-time approximation scheme, Ramsey theory, SIAM Journal on Computing, SNP (complexity), Springer Science+Business Media, SWAT and WADS conferences, Symposium on Discrete Algorithms, Theoretical computer science, Time complexity, Truth value, Vertex (graph theory), Vertex cover. Expand index (12 more) »
Algorithmica
Algorithmica is a monthly peer reviewed, scientific journal, published by Springer Science+Business Media focused on research and application of computer science algorithms.
New!!: Independent set (graph theory) and Algorithmica · See more »
Approximation algorithm
In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to NP-hard optimization problems with provable guarantees on the distance of the returned solution to the optimal one.
New!!: Independent set (graph theory) and Approximation algorithm · See more »
APX
In complexity theory the class APX (an abbreviation of "approximable") is the set of NP optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant (or constant-factor approximation algorithms for short).
New!!: Independent set (graph theory) and APX · See more »
Automatic label placement
Automatic label placement, sometimes called text placement or name placement, comprises the computer methods of placing labels automatically on a map or chart.
New!!: Independent set (graph theory) and Automatic label placement · See more »
Bipartite graph
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V such that every edge connects a vertex in U to one in V. Vertex sets U and V are usually called the parts of the graph.
New!!: Independent set (graph theory) and Bipartite graph · See more »
Brute-force search
In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's statement.
New!!: Independent set (graph theory) and Brute-force search · See more »
BSD licenses
BSD licenses are a family of permissive free software licenses, imposing minimal restrictions on the use and redistribution of covered software.
New!!: Independent set (graph theory) and BSD licenses · See more »
Chordal graph
In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle.
New!!: Independent set (graph theory) and Chordal graph · See more »
Claw-free graph
In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph.
New!!: Independent set (graph theory) and Claw-free graph · See more »
Clique (graph theory)
In the mathematical area of graph theory, a clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent; that is, its induced subgraph is complete.
New!!: Independent set (graph theory) and Clique (graph theory) · See more »
Clique problem
In computer science, the clique problem is the computational problem of finding cliques (subsets of vertices, all adjacent to each other, also called complete subgraphs) in a graph.
New!!: Independent set (graph theory) and Clique problem · See more »
Cograph
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 and disjoint union.
New!!: Independent set (graph theory) and Cograph · See more »
Combinatorica
Combinatorica is an international journal of mathematics, publishing papers in the fields of combinatorics and computer science.
New!!: Independent set (graph theory) and Combinatorica · See more »
Complement graph
In graph theory, the complement or inverse of a graph is a graph on the same vertices such that two distinct vertices of are adjacent if and only if they are not adjacent in.
New!!: Independent set (graph theory) and Complement graph · See more »
Computational problem
In theoretical computer science, a computational problem is a mathematical object representing a collection of questions that computers might be able to solve.
New!!: Independent set (graph theory) and Computational problem · See more »
Computer science
Computer science deals with the theoretical foundations of information and computation, together with practical techniques for the implementation and application of these foundations.
New!!: Independent set (graph theory) and Computer science · See more »
Cycle graph
In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain.
New!!: Independent set (graph theory) and Cycle graph · See more »
Dense graph
In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges.
New!!: Independent set (graph theory) and Dense graph · See more »
Dominating set
In graph theory, a dominating set for a graph G.
New!!: Independent set (graph theory) and Dominating set · See more »
Earliest deadline first scheduling
Earliest deadline first (EDF) or least time to go is a dynamic priority scheduling algorithm used in real-time operating systems to place processes in a priority queue.
New!!: Independent set (graph theory) and Earliest deadline first scheduling · See more »
Edge cover
In graph theory, an edge cover of a graph is a set of edges such that every vertex of the graph is incident to at least one edge of the set.
New!!: Independent set (graph theory) and Edge cover · See more »
Glossary of graph theory terms
This is a glossary of graph theory terms.
New!!: Independent set (graph theory) and Glossary of graph theory terms · See more »
GNU General Public License
The GNU General Public License (GNU GPL or GPL) is a widely used free software license, which guarantees end users the freedom to run, study, share and modify the software.
New!!: Independent set (graph theory) and GNU General Public License · See more »
Graph (discrete mathematics)
In mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related".
New!!: Independent set (graph theory) and Graph (discrete mathematics) · See more »
Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints.
New!!: Independent set (graph theory) and Graph coloring · See more »
Graph minor
In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges and vertices and by contracting edges.
New!!: Independent set (graph theory) and Graph minor · See more »
Graph theory
In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects.
New!!: Independent set (graph theory) and Graph theory · See more »
Greedy algorithm
A greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of making the locally optimal choice at each stage with the intent of finding a global optimum.
New!!: Independent set (graph theory) and Greedy algorithm · See more »
Information and Computation
Information and Computation is a computer science journal published by Elsevier (formerly Academic Press).
New!!: Independent set (graph theory) and Information and Computation · See more »
Intersection graph
In the mathematical area of graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets.
New!!: Independent set (graph theory) and Intersection graph · See more »
Interval graph
In graph theory, an interval graph is the intersection graph of a family of intervals on the real line.
New!!: Independent set (graph theory) and Interval graph · See more »
Job scheduler
A job scheduler is a computer application for controlling unattended background program execution of jobs.
New!!: Independent set (graph theory) and Job scheduler · See more »
Journal of Combinatorial Theory
The Journal of Combinatorial Theory, Series A and Series B, are mathematical journals specializing in combinatorics and related areas.
New!!: Independent set (graph theory) and Journal of Combinatorial Theory · See more »
Journal of the ACM
The Journal of the ACM is a peer-reviewed scientific journal covering computer science in general, especially theoretical aspects.
New!!: Independent set (graph theory) and Journal of the ACM · See more »
Kőnig's theorem (graph theory)
In the mathematical area of graph theory, Kőnig's theorem, proved by, describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs.
New!!: Independent set (graph theory) and Kőnig's theorem (graph theory) · See more »
Lecture Notes in Computer Science
Springer Lecture Notes in Computer Science (LNCS) is a series of computer science books published by Springer Science+Business Media (formerly Springer-Verlag) since 1973.
New!!: Independent set (graph theory) and Lecture Notes in Computer Science · See more »
Matching (graph theory)
In the mathematical discipline of graph theory, a matching or independent edge set in a graph is a set of edges without common vertices.
New!!: Independent set (graph theory) and Matching (graph theory) · See more »
Maximal independent set
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.
New!!: Independent set (graph theory) and Maximal independent set · See more »
Modular decomposition
In graph theory, the modular decomposition is a decomposition of a graph into subsets of vertices called modules. A module is a generalization of a connected component of a graph.
New!!: Independent set (graph theory) and Modular decomposition · See more »
NetworkX
NetworkX is a Python library for studying graphs and networks.
New!!: Independent set (graph theory) and NetworkX · See more »
NP-completeness
In computational complexity theory, an NP-complete decision problem is one belonging to both the NP and the NP-hard complexity classes.
New!!: Independent set (graph theory) and NP-completeness · See more »
NP-hardness
NP-hardness (''n''on-deterministic ''p''olynomial-time hardness), in computational complexity theory, is the defining property of a class of problems that are, informally, "at least as hard as the hardest problems in NP".
New!!: Independent set (graph theory) and NP-hardness · See more »
Optimization problem
In mathematics and computer science, an optimization problem is the problem of finding the best solution from all feasible solutions.
New!!: Independent set (graph theory) and Optimization problem · See more »
Padovan sequence
The Padovan sequence is the sequence of integers P(n) defined by the initial values and the recurrence relation The first few values of P(n) are The Padovan sequence is named after Richard Padovan who attributed its discovery to Dutch architect Hans van der Laan in his 1994 essay Dom.
New!!: Independent set (graph theory) and Padovan sequence · See more »
Partition of a set
In mathematics, a partition of a set is a grouping of the set's elements into non-empty subsets, in such a way that every element is included in one and only one of the subsets.
New!!: Independent set (graph theory) and Partition of a set · See more »
Path graph
In the mathematical field of graph theory, a path graph or linear graph is a graph whose vertices can be listed in the order v1, v2, …, vn such that the edges are where i.
New!!: Independent set (graph theory) and Path graph · See more »
Perfect graph
In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph.
New!!: Independent set (graph theory) and Perfect graph · See more »
Perrin number
In mathematics, the Perrin numbers are defined by the recurrence relation with initial values The sequence of Perrin numbers starts with The number of different maximal independent sets in an -vertex cycle graph is counted by the th Perrin number for.
New!!: Independent set (graph theory) and Perrin number · See more »
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints.
New!!: Independent set (graph theory) and Planar graph · See more »
Plastic number
In mathematics, the plastic number (also known as the plastic constant, the minimal Pisot number, the platin number, Siegel's number or, in French, le nombre radiant) is a mathematical constant which is the unique real solution of the cubic equation It has the exact value Its decimal expansion begins with.
New!!: Independent set (graph theory) and Plastic number · See more »
Polynomial-time approximation scheme
In computer science, a polynomial-time approximation scheme (PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems).
New!!: Independent set (graph theory) and Polynomial-time approximation scheme · See more »
Ramsey theory
Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of mathematics that studies the conditions under which order must appear.
New!!: Independent set (graph theory) and Ramsey theory · See more »
SIAM Journal on Computing
The SIAM Journal on Computing is a scientific journal focusing on the mathematical and formal aspects of computer science.
New!!: Independent set (graph theory) and SIAM Journal on Computing · See more »
SNP (complexity)
In computational complexity theory, SNP (from Strict NP) is a complexity class containing a limited subset of NP based on its logical characterization in terms of graph-theoretical properties.
New!!: Independent set (graph theory) and SNP (complexity) · See more »
Springer Science+Business Media
Springer Science+Business Media or Springer, part of Springer Nature since 2015, is a global publishing company that publishes books, e-books and peer-reviewed journals in science, humanities, technical and medical (STM) publishing.
New!!: Independent set (graph theory) and Springer Science+Business Media · See more »
SWAT and WADS conferences
WADS, the Algorithms and Data Structures Symposium, is an international academic conference in the field of computer science, focusing on algorithms and data structures.
New!!: Independent set (graph theory) and SWAT and WADS conferences · See more »
Symposium on Discrete Algorithms
The Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) is an academic conference in the fields of algorithm design and discrete mathematics.
New!!: Independent set (graph theory) and Symposium on Discrete Algorithms · See more »
Theoretical computer science
Theoretical computer science, or TCS, is a subset of general computer science and mathematics that focuses on more mathematical topics of computing and includes the theory of computation.
New!!: Independent set (graph theory) and Theoretical computer science · See more »
Time complexity
In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm.
New!!: Independent set (graph theory) and Time complexity · See more »
Truth value
In logic and mathematics, a truth value, sometimes called a logical value, is a value indicating the relation of a proposition to truth.
New!!: Independent set (graph theory) and Truth value · See more »
Vertex (graph theory)
In mathematics, and more specifically in graph theory, a vertex (plural vertices) or node is the fundamental unit of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges (unordered pairs of vertices), while a directed graph consists of a set of vertices and a set of arcs (ordered pairs of vertices).
New!!: Independent set (graph theory) and Vertex (graph theory) · See more »
Vertex cover
In the mathematical discipline of graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set.
New!!: Independent set (graph theory) and Vertex cover · See more »
Redirects here:
Coclique, Independence (graph theory), Independence number, Independent Set problem, Independent set problem, Maximum independent set, Maximum independent set problem, Maximum independent-set, Vertex independent set, Vertex packing.
References
[1] https://en.wikipedia.org/wiki/Independent_set_(graph_theory)
