Related Research Articles
Manuel Blum is a Venezuelan born American computer scientist who received the Turing Award in 1995 "In recognition of his contributions to the foundations of computational complexity theory and its application to cryptography and program checking".
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.
In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.
In graph theory, the perfect graph theorem of László Lovász states that an undirected graph is perfect if and only if its complement graph is also perfect. This result had been conjectured by Berge, and it is sometimes called the weak perfect graph theorem to distinguish it from the strong perfect graph theorem characterizing perfect graphs by their forbidden induced subgraphs.
In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. L(G) is constructed in the following way: for each edge in G, make a vertex in L(G); for every two edges in G that have a vertex in common, make an edge between their corresponding vertices in L(G).
In graph theory, the strong perfect graph theorem is a forbidden graph characterization of the perfect graphs as being exactly the graphs that have neither odd holes nor odd antiholes. It was conjectured by Claude Berge in 1961. A proof by Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas was announced in 2002 and published by them in 2006.
In the mathematical field of graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two distinct vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and removes all the edges that were previously there.
George Neil Robertson is a mathematician working mainly in topological graph theory, currently a distinguished professor emeritus at the Ohio State University.
Paul D. Seymour is a British mathematician known for his work in discrete mathematics, especially graph theory. He was responsible for important progress on regular matroids and totally unimodular matrices, the four colour theorem, linkless embeddings, graph minors and structure, the perfect graph conjecture, the Hadwiger conjecture, claw-free graphs, χ-boundedness, and the Erdős–Hajnal conjecture. Many of his recent papers are available from his website.
Dana Randall is an American computer scientist. She works as the ADVANCE Professor of Computing, and adjunct professor of mathematics at the Georgia Institute of Technology. She is also an External Professor of the Santa Fe Institute. Previously she was executive director of the Georgia Tech Institute of Data Engineering and Science (IDEaS) that she co-founded, and director of the Algorithms and Randomness Center. Her research include combinatorics, computational aspects of statistical mechanics, Monte Carlo stimulation of Markov chains, and randomized algorithms.
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 graphs have also been called transitively orientable graphs, partially orderable graphs, containment graphs, and divisor graphs. An incomparability graph is an undirected graph that connects pairs of elements that are not comparable to each other in a partial order.
Václav (Vašek) Chvátal is a Professor Emeritus in the Department of Computer Science and Software Engineering at Concordia University in Montreal, Quebec, Canada, and a visiting professor at Charles University in Prague. He has published extensively on topics in graph theory, combinatorics, and combinatorial optimization.
In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph.
Maria Chudnovsky is an Israeli-American mathematician working on graph theory and combinatorial optimization. She is a 2012 MacArthur Fellow.
In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence and assigns each vertex its first available color. Greedy colorings can be found in linear time, but they do not, in general, use the minimum number of colors possible.
In the mathematical field of graph theory, the bull graph is a planar undirected graph with 5 vertices and 5 edges, in the form of a triangle with two disjoint pendant edges.
In graph theory, a skew partition of a graph is a partition of its vertices into two subsets, such that the induced subgraph formed by one of the two subsets is disconnected and the induced subgraph formed by the other subset is the complement of a disconnected graph. Skew partitions play an important role in the theory of perfect graphs.
Bruce Alan ReedFRSC is a Canadian mathematician and computer scientist, a former Canada Research Chair in Graph Theory at McGill University. His research is primarily in graph theory. He is a distinguished research fellow of the Institute of Mathematics in the Academia Sinica, Taiwan, and an adjunct professor at the University of Victoria in Canada.
Gérard Pierre Cornuéjols is the IBM University Professor of Operations Research in the Carnegie Mellon University Tepper School of Business and professor at Aix-Marseille University. His research interests include facility location, integer programming, balanced matrices, and perfect graphs.
Daniel Mier Gusfield is an American computer scientist, Distinguished Professor of Computer Science at the University of California, Davis. Gusfield is known for his research in combinatorial optimization and computational biology.
References
- 1 2 Étude des stables dans les graphes sans étoile, Joseph Fourier University, 1978, retrieved 2024-10-16
- 1 2 3 Or_Afri_Icons 6: Pr. Najiba Sbihi, OR@AFRICA, 2024, retrieved 2024-10-16– via Linkedin
- ↑ Sbihi, Najiba; Fonlupt, Jean (January 1987), "Contribution à l'étude des stables dans un graphe par une approche algorithmique", Theses.fr, retrieved 2024-10-16
- ↑ Avis, David; Bondy, Adrian; Cook, William; Reed, Bruce (June 2007), "Vašek Chvátal: A Very Short Introduction" (PDF), Graphs and Combinatorics, 23 (S1): 41–65, doi:10.1007/s00373-007-0721-4
