New in 6.0
Enhanced Coverage of Intractable (NP-Complete) Problems
- Clique problem
- Vertex cover problem
- Independent set problem
- 3-satisfiability (3-SAT) problem
- 3-coloring of planar graphs
New in 5.5
- ShortestPathOneToAll calculates the shortest path from a starting node to all other nodes on a directed graph.
- ShortestPathAllToAll calculates simultaneously the shortest path from all nodes to all nodes on a directed graph.
Improved in 5.5
- AVLTreeInsert inserts a new key into a balanced binary search tree. The tree is rebalanced if necessary. AVLTreeInsert may be used to generate a balanced tree step by step from an empty tree.
- AVLTreeDelete deletes the node carrying the given key in a balanced tree. The tree is rebalanced if necessary.
New in 5.4
- NashEquilibrium returns one equilibrium point for Bimatrix Games where A and B are the payoff matrices of players 1 and 2, respectively.
- NashEquilibriumQ — NashEquilibriumQ tests whether strategies x, y correspond to an equilibrium point with respect to payoff matrices A, B.
- DynamicEvolution computes the time evolution of strategies based on a payoff matrix with initial strategies up to a final time.
Binary Search Trees
- GenerateAVLTree generates a balanced binary search tree from a given list of keys.
- AVLTreeInsert inserts a new key into a balanced binary search tree. The tree is rebalanced if necessary.
- AVLTreeDelete deletes the node carrying the given key in a tree. The tree is rebalanced if necessary.
- OptimalBinarySearchTree generates a binary search tree such that the average access time is minimized. The method is based on dynamic programming.
- ShowTree generates graph of binary tree.
- The graph algorithms have been extended by routines for binary search trees.
- The matrix game branch has given new routines.
New in 5.3
- MatrixGames calculates optimal strategies for two-person zero-sum games. The optimal strategy is in general a mixed one, where players 1 and 2 independently pick decisions (alternatives) si and tj, with probability xi and yj, respectively. Such optimal mixed strategies always exist. Payment to a player will be less if he deviates from his optimal strategy whereas the other player sticks to his optimal strategy (Nash equilibrium).
- Implemented a new routine DualSimplex that solves linear constrained problems with the dual simplex method
- Representation of graph routines graphically
- Linear optimization: revised simplex with sensitivity analysis and
- Shortest-path tasks: one-to-all and all-to-all shortest connections on
- Graph algorithms: calculations of flows on a graph
- Combinatorial optimization and heuristics: several routines that can
be used to solve assignment, traveling salesman and other problems and
can be used for implementation of additional effective heuristics
- Documentation fully compatible with Mathematica 7
- Completely new branch of problems: graph algorithms
- MaximumFlow: calculates the maximum flow on a network defined
list of links from a source node to a sink node
- MinCostsFlow: calculates the minimum costs flow on a network
source node to a sink node, at given net flow
- MinimalSpanningTree: calculates a minimal spanning tree of a
with not directed links; the algorithm of Prim is implemented
- BiConnectComp: calculates the list of articulation points and
biconnected components of a graph given by its link list
- StronglyConnectedComponents: calculates a list of subsets of
("block nodes") each inducing a strongly connected component of the
- TopologicalOrdering: calculates a reordered list of nodes if
topological ordering is possible; an empty is returned otherwise
- LCShortestPath: calculates the shortest path in a network
defined through a list of links; negative weights are allowed as long as
no negative cycles arise