Features
New in 6.0
Enhanced Coverage of Intractable (NPComplete) Problems
 Clique problem
 Vertex cover problem
 Independent set problem
 3satisfiability (3SAT) problem
 3coloring of planar graphs
New in 5.5
Graph Algorithms
 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
Graph Algorithms
 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
Game Theory
 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.
General Features
 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 twoperson zerosum 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).
General Features
 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
branchandbound methods
 Shortestpath tasks: onetoall and alltoall shortest connections on
a graph
 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
by a
list of links from a source node to a sink node
 MinCostsFlow: calculates the minimum costs flow on a network
from a
source node to a sink node, at given net flow
 MinimalSpanningTree: calculates a minimal spanning tree of a
network
with not directed links; the algorithm of Prim is implemented
 BiConnectComp: calculates the list of articulation points and
the
biconnected components of a graph given by its link list
 StronglyConnectedComponents: calculates a list of subsets of
nodes
("block nodes") each inducing a strongly connected component of the
directed graph
 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

