Posted inGraph Theory & Applications
Graph Theory – Connectivity
Whether it is possible to traverse a graph from one vertex to another is determined…
Posted inGraph Theory & Applications
Graph Theory – Trees
Trees are graphs that do not contain even a single cycle. They represent hierarchical structure…
Posted inGraph Theory & Applications
Graph Theory – Types of Graphs
There are various types of graphs depending upon the number of vertices, number of edges,…
Posted inDesign & Analysis of Algorithms
Maximum Matching in Bipartite Graphs
In many situations we are faced with a problem of pairing elements of two sets.…
Posted inDesign & Analysis of Algorithms
The Simplex Method
We have already encountered linear programming (see Section 6.6)—the general problem of optimizing a linear…
Posted inDesign & Analysis of Algorithms
Iterative Improvement
The greedy strategy, considered in the preceding chapter, constructs a solution to an optimization problem…
Posted inDesign & Analysis of Algorithms
Huffman Trees and Codes
Suppose we have to encode a text that comprises symbols from some n-symbol alphabet by assigning…
Posted inDesign & Analysis of Algorithms
Dijkstra’s Algorithm
In this section, we consider the single-source shortest-paths problem: for a given vertex called the source in a…
Posted inDesign & Analysis of Algorithms
Kruskal’s Algorithm
In the previous section, we considered the greedy algorithm that “grows” a mini-mum spanning tree…
Posted inDesign & Analysis of Algorithms
Prim’s Algorithm
The following problem arises naturally in many practical situations: given n points, connect them in the cheapest…