Greedy coloringIn 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. Different choices of the sequence of vertices will typically produce different colorings of the given graph, so much of the study of greedy colorings has concerned how to find a good ordering.
Competitive analysis (online algorithm)Competitive analysis is a method invented for analyzing online algorithms, in which the performance of an online algorithm (which must satisfy an unpredictable sequence of requests, completing each request without being able to see the future) is compared to the performance of an optimal offline algorithm that can view the sequence of requests in advance. An algorithm is competitive if its competitive ratio—the ratio between its performance and the offline algorithm's performance—is bounded.
Vertex (geometry)In geometry, a vertex (: vertices or vertexes) is a point where two or more curves, lines, or edges meet. As a consequence of this definition, the point where two lines meet to form an angle and the corners of polygons and polyhedra are vertices. The vertex of an angle is the point where two rays begin or meet, where two line segments join or meet, where two lines intersect (cross), or any appropriate combination of rays, segments, and lines that result in two straight "sides" meeting at one place.
24-cellIn geometry, the 24-cell is the convex regular 4-polytope (four-dimensional analogue of a Platonic solid) with Schläfli symbol {3,4,3}. It is also called C24, or the icositetrachoron, octaplex (short for "octahedral complex"), icosatetrahedroid, octacube, hyper-diamond or polyoctahedron, being constructed of octahedral cells. The boundary of the 24-cell is composed of 24 octahedral cells with six meeting at each vertex, and three at each edge. Together they have 96 triangular faces, 96 edges, and 24 vertices.
PentagonIn geometry, a pentagon (from the Greek πέντε pente meaning five and γωνία gonia meaning angle) is any five-sided polygon or 5-gon. The sum of the internal angles in a simple pentagon is 540°. A pentagon may be simple or self-intersecting. A self-intersecting regular pentagon (or star pentagon) is called a pentagram. A regular pentagon has Schläfli symbol {5} and interior angles of 108°. A regular pentagon has five lines of reflectional symmetry, and rotational symmetry of order 5 (through 72°, 144°, 216° and 288°).
Hungarian algorithmThe Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in polynomial time and which anticipated later primal–dual methods. It was developed and published in 1955 by Harold Kuhn, who gave the name "Hungarian method" because the algorithm was largely based on the earlier works of two Hungarian mathematicians: Dénes Kőnig and Jenő Egerváry. James Munkres reviewed the algorithm in 1957 and observed that it is (strongly) polynomial.
Blossom algorithmIn graph theory, the blossom algorithm is an algorithm for constructing maximum matchings on graphs. The algorithm was developed by Jack Edmonds in 1961, and published in 1965. Given a general graph G = (V, E), the algorithm finds a matching M such that each vertex in V is incident with at most one edge in M and is maximized. The matching is constructed by iteratively improving an initial empty matching along augmenting paths in the graph.
