|
Minimum Routing Cost Spanning Tree
In computer science, the minimum routing cost spanning tree of a weighted graph is a spanning tree minimizing the sum of pairwise distances between vertices in the tree. It is also called the optimum distance spanning tree, shortest total path length spanning tree, minimum total distance spanning tree, or minimum average distance spanning tree. In an unweighted graph, this is the spanning tree of minimum Wiener index. writes that the problem of constructing these trees was proposed by Francesco Maffioli. It is NP-hard to construct it, even for unweighted graphs. However, it has a polynomial-time approximation scheme. The approximation works by choosing a number k that depends on the approximation ratio but not on the number of vertices of the input graph, and by searching among all trees with k internal nodes. The minimum routing cost spanning tree of an unweighted interval graph can be constructed in linear time. A polynomial time algorithm is also known for distance-hereditary gr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Computer Science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (including the design and implementation of hardware and software). Computer science is generally considered an area of academic research and distinct from computer programming. Algorithms and data structures are central to computer science. The theory of computation concerns abstract models of computation and general classes of problems that can be solved using them. The fields of cryptography and computer security involve studying the means for secure communication and for preventing security vulnerabilities. Computer graphics and computational geometry address the generation of images. Programming language theory considers different ways to describe computational processes, and database theory concerns the management of repositories ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Weighted Graph
This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges Edge or EDGE may refer to: Technology Computing * Edge computing, a network load-balancing system * Edge device, an entry point to a computer network * Adobe Edge, a graphical development application * Microsoft Edge, a web browser developed by .... Symbols A B C D E F G H ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Spanning Tree
In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree (see about spanning forests below). If all of the edges of ''G'' are also edges of a spanning tree ''T'' of ''G'', then ''G'' is a tree and is identical to ''T'' (that is, a tree has a unique spanning tree and it is itself). Applications Several pathfinding algorithms, including Dijkstra's algorithm and the A* search algorithm, internally build a spanning tree as an intermediate step in solving the problem. In order to minimize the cost of power networks, wiring connections, piping, automatic speech recognition, etc., people often use algorithms that gradually build a spanning tree (or many such trees) as intermediate steps in the process of finding the minimum spanning tree. The Interne ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Wiener Index
In chemical graph theory, the Wiener index (also Wiener number) introduced by Harry Wiener, is a topological index of a molecule, defined as the sum of the lengths of the shortest paths between all pairs of vertices in the chemical graph representing the non-hydrogen atoms in the molecule.. Wiener index can be used for the representation of computer networks and enhancing lattice hardware security. History The Wiener index is named after Harry Wiener, who introduced it in 1947; at the time, Wiener called it the "path number".. It is the oldest topological index related to molecular branching. Based on its success, many other topological indexes of chemical graphs, based on information in the distance matrix of the graph, have been developed subsequently to Wiener's work. The same quantity has also been studied in pure mathematics, under various names including the gross status, the distance of a graph,. and the transmission. The Wiener index is also closely related to the closene ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
NP-hard
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard problem is the subset sum problem. A more precise specification is: a problem ''H'' is NP-hard when every problem ''L'' in NP can be reduced in polynomial time to ''H''; that is, assuming a solution for ''H'' takes 1 unit time, ''H''s solution can be used to solve ''L'' in polynomial time. As a consequence, finding a polynomial time algorithm to solve any NP-hard problem would give polynomial time algorithms for all the problems in NP. As it is suspected that P≠NP, it is unlikely that such an algorithm exists. It is suspected that there are no polynomial-time algorithms for NP-hard problems, but that has not been proven. Moreover, the class P, in which all problems can be solved in polynomial time, is contained in the NP class. Def ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Polynomial-time Approximation Scheme
In computer science (particularly algorithmics), a polynomial-time approximation scheme (PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems). A PTAS is an algorithm which takes an instance of an optimization problem and a parameter and produces a solution that is within a factor of being optimal (or for maximization problems). For example, for the Euclidean traveling salesman problem, a PTAS would produce a tour with length at most , with being the length of the shortest tour. The running time of a PTAS is required to be polynomial in the problem size for every fixed ε, but can be different for different ε. Thus an algorithm running in time or even counts as a PTAS. Variants Deterministic A practical problem with PTAS algorithms is that the exponent of the polynomial could increase dramatically as ε shrinks, for example if the runtime is . One way of addressing this is to define the efficient polynomial-ti ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Interval Graph
In graph theory, an interval graph is an undirected graph formed from a set of intervals on the real line, with a vertex for each interval and an edge between vertices whose intervals intersect. It is the intersection graph of the intervals. Interval graphs are chordal graphs and perfect graphs. They can be recognized in linear time, and an optimal graph coloring or maximum clique in these graphs can be found in linear time. The interval graphs include all proper interval graphs, graphs defined in the same way from a set of unit intervals. These graphs have been used to model food webs, and to study scheduling problems in which one must select a subset of tasks to be performed at non-overlapping times. Other applications include assembling contiguous subsequences in DNA mapping, and temporal reasoning. Definition An interval graph is an undirected graph formed from a family of intervals :S_i,\quad i=0,1,2,\dots by creating one vertex for each interval , and connecting ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Distance-hereditary Graph
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 in any connected induced subgraph are the same as they are in the original graph. Thus, any induced subgraph inherits the distances of the larger graph. Distance-hereditary graphs were named and first studied by , although an equivalent class of graphs was already shown to be perfect in 1970 by Olaru and Sachs. It has been known for some time that the distance-hereditary graphs constitute an intersection class of graphs, but no intersection model was known until one was given by . Definition and characterization The original definition of a distance-hereditary graph is a graph such that, if any two vertices and belong to a connected induced subgraph of , then some shortest path connecting and in must be a subgraph of , so that the distance between and in is the same as the distance in . Distance-hereditary graphs ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Greedy Algorithm
A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time. For example, a greedy strategy for the travelling salesman problem (which is of high computational complexity) is the following heuristic: "At each step of the journey, visit the nearest unvisited city." This heuristic does not intend to find the best solution, but it terminates in a reasonable number of steps; finding an optimal solution to such a complex problem typically requires unreasonably many steps. In mathematical optimization, greedy algorithms optimally solve combinatorial problems having the properties of matroids and give constant-factor approximations to optimization problems with the submodular structure. Specifics Greedy algo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Egalitarian Rule
In social choice and operations research, the egalitarian rule (also called the max-min rule or the Rawlsian rule) is a rule saying that, among all possible alternatives, society should pick the alternative which maximizes the ''minimum utility'' of all individuals in society. It is a formal mathematical representation of the egalitarian philosophy. It also corresponds to John Rawls' principle of maximizing the welfare of the worst-off individual. Definition Let X be a set of possible `states of the world' or `alternatives'. Society wishes to choose a single state from X. For example, in a single-winner election, X may represent the set of candidates; in a resource allocation setting, X may represent all possible allocations. Let I be a finite set, representing a collection of individuals. For each i \in I, let u_i:X\longrightarrow\mathbb be a ''utility function'', describing the amount of happiness an individual ''i'' derives from each possible state. A '' social choice rule' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Choquet Integral
A Choquet integral is a subadditive or superadditive integral created by the French mathematician Gustave Choquet in 1953. It was initially used in statistical mechanics and potential theory, but found its way into decision theory in the 1980s, where it is used as a way of measuring the expected utility of an uncertain event. It is applied specifically to membership functions and capacities. In imprecise probability theory, the Choquet integral is also used to calculate the lower expectation induced by a 2-monotone lower probability, or the upper expectation induced by a 2-alternating upper probability. Using the Choquet integral to denote the expected utility of belief functions measured with capacities is a way to reconcile the Ellsberg paradox and the Allais paradox. Definition The following notation is used: * S – a set. * \mathcal – a collection of subsets of S. * f : S\to \mathbb – a function. * \nu : \mathcal\to \mathbb^+ – a monotone set function. Assume t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Optimal Network Design
Optimal network design is a problem in combinatorial optimization. It is an abstract representation of the problem faced by states and municipalities when they plan their road network. Given a set of locations to connect by roads, the objective is to have a short traveling distance between every two points. More specifically, the goal is to minimize the ''sum'' of shortest distances, where the sum is taken over all pairs of points. For each two locations, there is a number representing the cost of building a direct road between them. A decision must be made about which roads to build with a fixed budget. Formal definition The input to the optimal network design problem is a weighted graph ''G'' = (V,E), where the weight of each edge (u,v) in the graph represents the cost of building a road from u to v; and a budget ''B''. A ''feasible network'' is a subset S of E, such that the sum of w(u,v) for all (u,v) in S is at most B, and there is a path between every two nodes u and v (th ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
