Algorithms and Data Structures Glossary (Starting with "V")

Free glossaries at TanslationDirectory.com

Algorithms and Data Structures Glossary
(Starting with "V")

By www.nist.gov,
Gaithersburg, Maryland, U.S.A.

paul . black [at] nist . gov
http://www.nist.gov/dads

Become a member of TranslationDirectory.com at just $12 per month (paid per year)

Advertisements:

Use the search bar to look for terms in all glossaries, dictionaries, articles and other resources simultaneously

A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

van Emde-Boas priority queue

(data structure)

Definition: An efficient implementation of priority queues where insert, delete, get minimum, get maximum, etc. take O(log log N) time, where N is the total possible number of keys. Depending on the circumstance, the implementation is null (if the queue is empty), an integer (if the queue has one integer), a bit vector of size N (if N is small), or a special data structure: an array of priority queues, called the bottom queues, and one more priority queue of array indexes of the bottom queues.

Generalization (I am a kind of ...)
priority queue.

Aggregate child (... is a part of or used in me.)
bit vector, array.

Note: After [GBY91, pages 216-217].

Author: PEB

More information

P. van Emde-Boas, R. Kass, and E. Zijlstra, Design and Implementation of an Efficient Priority Queue, Mathematical Systems Theory, 10:99-127, 1977.
P. van Emde-Boas, Preserving Order in a Forest in Less than Logarithmic Time and Linear Space, Inf. Proc. Letters, 6(3):80-82, June 1977.

vehicle routing problem

(classic problem)

Definition: Find an optimal route of one or more vehicles through a graph.

Also known as VRP.

Generalization (I am a kind of ...)
optimization problem.

Specialization (... is a kind of me.)
traveling salesman.

Note: The vehicles may be school buses, garbage trucks, delivery vans, etc. The optimal may be fastest routes, least variation (all get nearly equal assignments), least "cost" (big cost for going through Mayor's neighborhood, small cost for taking freeway), etc.

With one vehicle, this is the traveling salesman problem.

Author: PEB

Venn diagram

(definition)

Definition: A visual depiction of membership in sets according to binary properties, using overlapping ovals to divide the plane into regions. Regions inside an oval have the property the oval represents, while regions outside it do not have the property. Regions are shaded to show combinations of properties (or sets) of interest, or elements are placed in regions corresponding to their properties (or membership).

Note: Here is an example of a Venn diagram with three properties: male/female, happy/sad, and short/tall. Some of the combinations, such as sad, tall males and happy, short females are labeled.

John Venn first published these diagrams in 1880, although similar diagrams were used much earlier by Leibniz and Euler (Opera Omnia), a century earlier.

Author: PEB

vertex

(definition)

Definition: An item in a graph. Sometimes referred to as a node.

Specialization (... is a kind of me.)
cut vertex, free vertex, matched vertex, Steiner vertex.

Aggregate child (... is a part of or used in me.)
in-degree, out-degree.

Note: The plural is vertices. Another plural is vertexes.

Author: PEB

vertex coloring

(definition)

Definition: An assignment of colors (or any distinct marks) to the vertices of a graph. Strictly speaking, a coloring is proper if no two adjacent vertices have the same color.

Note: From Algorithms and Theory of Computation Handbook, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Authors: PEB,CRC-A

vertex connectivity

(definition)

Definition: (1) The smallest number of vertices whose deletion causes a connected graph to not be connected. (2) For a pair of vertices s and t in a graph, the smallest number of vertices whose deletion will separate s from t.

Author: GS

vertex cover

(classic problem)

Definition: A set of vertices in an undirected graph where every edge connects at least one vertex. The vertex cover problem is to find a minimum size set and is NP-complete.

Note: An illustration of vertex cover is posting the least number of polices to watch every street in a city. Clearly police should be at intersections. What's the smallest set of intersections?

To correspond to the vertex cover problem, streets must be straight. A curving street is divided into segments such that at any intersection, a person can see from that intersection to the next. Also, no street goes straight through an intersection.

Author: PEB

vertical visibility map

(definition)

Definition: A partition of the plane into regions by drawing a vertical straight line through each vertex p of a planar straight-line graph until it intersects an edge e of the graph or extends to infinity. The edge e is said to be vertically visible from p.

Note: From Algorithms and Theory of Computation Handbook, page 19-27, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

visibility map

(definition)

Definition: A planar subdivision that encodes the visibility information, that is, which points are mutually visible.

Author: CRC-A

visible

(definition)

Definition: Two points p and q are visible if the straight line segment between them does not intersect any other object, edge, etc.

Note: Visibility is symmetric, that is, if p is visible from q, q is visible from p.
From Algorithms and Theory of Computation Handbook, page 19-27, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

Viterbi algorithm

(algorithm)

Definition: An algorithm to compute the optimal (most likely) state sequence in a hidden Markov model given a sequence of observed outputs.

Aggregate child (... is a part of or used in me.)
hidden Markov model.

Note: Also used to decode, i.e. remove noise from, linear error-correcting codes.

Author: PEB

Vitter's algorithm

(algorithm)

Definition: An adaptive Huffman coding scheme. Typically this produces codings the same length as or shorter than static Huffman coding. In the worst case, this uses one more bit per codeword.

Generalization (I am a kind of ...)
adaptive Huffman coding.

Aggregate child (... is a part of or used in me.)
full binary tree.

Author: PEB

More information

Jeffrey Scott Vitter, Design and analysis of dynamic Huffman codes, Journal of the ACM 34(4):825-845, October 1987.
Jeffrey Scott Vitter, ALGORITHM 673: dynamic Huffman coding, ACM Transactions on Mathematical Software, 15(2):158-167, June 1989.

A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z