|
Graph Algorithms
The following is a list of well-known algorithms along with one-line descriptions for each. Automated planning Combinatorial algorithms General combinatorial algorithms * Brent's algorithm: finds a cycle in function value iterations using only two iterators * Floyd's cycle-finding algorithm: finds a cycle in function value iterations * Gale–Shapley algorithm: solves the stable marriage problem * Pseudorandom number generators (uniformly distributed—see also List of pseudorandom number generators for other PRNGs with varying degrees of convergence and varying statistical quality): ** ACORN generator ** Blum Blum Shub ** Lagged Fibonacci generator ** Linear congruential generator ** Mersenne Twister Graph algorithms * Coloring algorithm: Graph coloring algorithm. * Hopcroft–Karp algorithm: convert a bipartite graph to a maximum cardinality matching * Hungarian algorithm: algorithm for finding a perfect matching * Prüfer coding: conversion between a labeled tree an ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing. More advanced algorithms can perform automated deductions (referred to as automated reasoning) and use mathematical and logical tests to divert the code execution through various routes (referred to as automated decision-making). Using human characteristics as descriptors of machines in metaphorical ways was already practiced by Alan Turing with terms such as "memory", "search" and "stimulus". In contrast, a heuristic is an approach to problem solving that may not be fully specified or may not guarantee correct or optimal results, especially in problem domains where there is no well-defined correct or optimal result. As an effective method, an algorithm can be expressed within a finite amount of space ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Tarjan's Off-line Lowest Common Ancestors Algorithm
In computer science, Tarjan's off-line lowest common ancestors algorithm is an algorithm for computing lowest common ancestors for pairs of nodes in a tree, based on the union-find data structure. The lowest common ancestor of two nodes ''d'' and ''e'' in a rooted tree ''T'' is the node ''g'' that is an ancestor of both ''d'' and ''e'' and that has the greatest depth in ''T''. It is named after Robert Tarjan, who discovered the technique in 1979. Tarjan's algorithm is an offline algorithm; that is, unlike other lowest common ancestor algorithms, it requires that all pairs of nodes for which the lowest common ancestor is desired must be specified in advance. The simplest version of the algorithm uses the union-find data structure, which unlike other lowest common ancestor data structures can take more than constant time per operation when the number of pairs of nodes is similar in magnitude to the number of nodes. A later refinement by speeds the algorithm up to linear time. Pseudo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Maximum Flow
In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate. The maximum flow problem can be seen as a special case of more complex network flow problems, such as the circulation problem. The maximum value of an s-t flow (i.e., flow from source s to sink t) is equal to the minimum capacity of an s-t cut (i.e., cut severing s from t) in the network, as stated in the max-flow min-cut theorem. History The maximum flow problem was first formulated in 1954 by T. E. Harris and F. S. Ross as a simplified model of Soviet railway traffic flow. In 1955, Lester R. Ford, Jr. and Delbert R. Fulkerson created the first known algorithm, the Ford–Fulkerson algorithm.Ford, L.R., Jr.; Fulkerson, D.R., ''Flows in Networks'', Princeton University Press (1962). In their 1955 paper, Ford and Fulkerson wrote that the problem of Harris and Ross is formulated as follows (see p. 5):Consider a rail network c ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Strongly Polynomial
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor. Since an algorithm's running time may vary among different inputs of the same size, one commonly considers the worst-case time complexity, which is the maximum amount of time required for inputs of a given size. Less common, and usually specified explicitly, is the average-case complexity, which is the average of the time taken on inputs of a given size (this makes sense because there are only a finite number of possible inputs of a given size). In both cases, the time complexity is generally expressed ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Dinic's Algorithm
Dinic's algorithm or Dinitz's algorithm is a strongly polynomial algorithm for computing the maximum flow in a flow network, conceived in 1970 by Israeli (formerly Soviet) computer scientist Yefim (Chaim) A. Dinitz. The algorithm runs in O(V^2 E) time and is similar to the Edmonds–Karp algorithm, which runs in O(VE^2) time, in that it uses shortest augmenting paths. The introduction of the concepts of the ''level graph'' and ''blocking flow'' enable Dinic's algorithm to achieve its performance. History Yefim Dinitz invented this algorithm in response to a pre-class exercise in Adelson-Velsky's algorithms class. At the time he was not aware of the basic facts regarding the Ford–Fulkerson algorithm. Dinitz mentions inventing his algorithm in January 1969, which was published in 1970 in the journal ''Doklady Akademii Nauk SSSR''. In 1974, Shimon Even and (his then Ph.D. student) Alon Itai at the Technion in Haifa were very curious and intrigued by Dinitz's algorithm as well as ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Flow Network
In graph theory, a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in operations research, a directed graph is called a network, the vertices are called nodes and the edges are called arcs. A flow must satisfy the restriction that the amount of flow into a node equals the amount of flow out of it, unless it is a source, which has only outgoing flow, or sink, which has only incoming flow. A network can be used to model traffic in a computer network, circulation with demands, fluids in pipes, currents in an electrical circuit, or anything similar in which something travels through a network of nodes. Definition A network is a graph , where is a set of vertices and is a set of 's edges – a subset of – together with a non-negative function , called the capacity function. Without loss of generality, we may assume t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
TrustRank
TrustRank is an algorithm that conducts link analysis to separate useful webpages from spam and helps search engine rank pages in SERPs (Search Engine Results Pages). It is semi-automated process which means that it needs some human assistance in order to function properly. Search engines have many different algorithms and ranking factors that they use when measuring the quality of webpages. TrustRank is one of them. Because manual review of the Internet is impractical and very expensive, TrustRank was introduced in order to help achieve this task much faster and cheaper. It was first introduced by researchers Zoltan Gyongyi and Hector Garcia-Molina of Stanford University and Jan Pedersen of Yahoo! in their paper "Combating Web Spam with TrustRank" in 2004. Today, this algorithm is a part of major web search engines like Yahoo! and Google. One of the most important factors that help web search engine determine the quality of a web page when returning results are backlinks. S ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
PageRank
PageRank (PR) is an algorithm used by Google Search to rank webpages, web pages in their search engine results. It is named after both the term "web page" and co-founder Larry Page. PageRank is a way of measuring the importance of website pages. According to Google: Currently, PageRank is not the only algorithm used by Google to order search results, but it is the first algorithm that was used by the company, and it is the best known. As of September 24, 2019, PageRank and all associated patents are expired. Description PageRank is a Network theory#Link analysis, link analysis algorithm and it assigns a numerical weighting to each element of a hyperlinked Set (computer science), set of documents, such as the World Wide Web, with the purpose of "measuring" its relative importance within the set. The algorithm may be applied to any collection of entities with reciprocal link, reciprocal quotations and references. The numerical weight that it assigns to any given element ''E'' is r ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hubs And Authorities
Hyperlink-Induced Topic Search (HITS; also known as hubs and authorities) is a link analysis algorithm that rates Web pages, developed by Jon Kleinberg. The idea behind Hubs and Authorities stemmed from a particular insight into the creation of web pages when the Internet was originally forming; that is, certain web pages, known as hubs, served as large directories that were not actually authoritative in the information that they held, but were used as compilations of a broad catalog of information that led users direct to other authoritative pages. In other words, a good hub represents a page that pointed to many other pages, while a good authority represents a page that is linked by many different hubs. The scheme therefore assigns two scores for each page: its authority, which estimates the value of the content of the page, and its hub value, which estimates the value of its links to other pages. History In journals Many methods have been used to rank the importance of scienti ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hyperlink-Induced Topic Search
Hyperlink-Induced Topic Search (HITS; also known as hubs and authorities) is a link analysis algorithm that rates Web pages, developed by Jon Kleinberg. The idea behind Hubs and Authorities stemmed from a particular insight into the creation of web pages when the Internet was originally forming; that is, certain web pages, known as hubs, served as large directories that were not actually authoritative in the information that they held, but were used as compilations of a broad catalog of information that led users direct to other authoritative pages. In other words, a good hub represents a page that pointed to many other pages, while a good authority represents a page that is linked by many different hubs. The scheme therefore assigns two scores for each page: its authority, which estimates the value of the content of the page, and its hub value, which estimates the value of its links to other pages. History In journals Many methods have been used to rank the importance of scienti ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Girvan–Newman Algorithm
The Girvan–Newman algorithm (named after Michelle Girvan and Mark Newman) is a hierarchical method used to detect communities in complex systems.Girvan M. and Newman M. E. J.Community structure in social and biological networks Proc. Natl. Acad. Sci. USA 99, 7821–7826 (2002) Edge betweenness and community structure The Girvan–Newman algorithm detects communities by progressively removing edges from the original network. The connected components of the remaining network are the communities. Instead of trying to construct a measure that tells us which edges are the most central to communities, the Girvan–Newman algorithm focuses on edges that are most likely "between" communities. Vertex betweenness is an indicator of highly central nodes in networks. For any node i, vertex betweenness is defined as the fraction of shortest paths between pairs of nodes that run through it. It is relevant to models where the network modulates transfer of goods between known start and end n ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Spectral Layout
Spectral layout is a class of algorithm for drawing graphs. The layout uses the eigenvectors of a matrix, such as the Laplace matrix of the graph, as Cartesian coordinate A Cartesian coordinate system (, ) in a plane is a coordinate system that specifies each point uniquely by a pair of numerical coordinates, which are the signed distances to the point from two fixed perpendicular oriented lines, measured in ...s of the graph's vertices. The idea of the layout is to compute the two largest (or smallest) eigenvalues and corresponding eigenvectors of the Laplacian matrix of the graph and then use those for actually placing the nodes. Usually nodes are placed in the 2 dimensional plane. An embedding into more dimensions can be found by using more eigenvectors. In the 2-dimensional case, for a given node which corresponds to the row/column i in the (symmetric) Laplacian matrix L of the graph, the x and y-coordinates are the i-th entries of the first and second eigenvectors of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
