Graph algorithm Lengauer Tarjan Dominator Tree is applied in many routing applications, one application can be if the user wants to go from city A to city B and there are multiple routes but all the routes are diverting from city X then the user can find out city X by using this algorithm. The first part of this project is to provide support for Lengauer Tarjan Dominator Tree in pgRouting and the second part of this project is to provide support for check any given graph is bipartite or not. If the graph is bipartite then function returns the vertex along with two colors 0 and 1 which represents two different sets. If graph is not bipartite then algorithm returns an empty set. The algorithms are going to be taken from the Boost Graph Library (BGL).

Organization

Student

Prakash Tiwari

Mentors

  • cvvergara
  • Aasheesh Tiwari
close

2020