Link to pdf version.
Introduction : In this article I am going to explain the concept of Dominators in a directed graph, its applications and an efficient algorithm for construction of dominator tree published by Robert Tarjan .
Since there is a lot of content to be covered, the post is going to be a bit long. So, please be patient. 🙂
Pr-requisites : dfs in directed graphs. DSU
Continue reading “Dominator Tree of a Directed Graph”
Introduction : Centroid Decomposition is just a divide and conquer technique which is used on trees and turns out useful in many problems. It is also known as “Separator Decomposition”. In this article I will first explain How do we do centroid decomposition followed by it’s applications (i.e. Why do we do it ? ) . In the end, I will discuss a few problems that can be easily solved using centroid decomposition.
So, let’s begin 🙂
Pr-requisites : Basic graph theory. DFS . (Basic) Divide and Conquer.
Continue reading “Centroid Decomposition of a Tree”
Introduction : Bridge Tree is a term coined by me that refers to the tree formed by shrinking 2-edge biconnected components of the graph . The 2-edge biconnected components shall be referred to as “bridge components” in the further post. The concept is very intuitive so let’s see more about it.
Pre-requisites : Basic Graph Theory. Dfs and Bfs .Bridges in a graph. Biconnected Components and Block-Cut Tree (not really needed to understand but experience with this would be helpful in easier imagination :))
Continue reading “The “Bridge Tree” of a graph”