This is a C Program to solve TSP. The Traveling Salesman Problem states that, given a list of cities and the distances between each pair of cities, calculate the shortest distance route that visits each city exactly once and route returns to original city. It is an NP-hard problem. Here is source code of the … Read more
This is a C Program to check if a graph is Bipartite. A bipartite graph or bigraph is a graph whose vertices can be divided into two disjoint sets P and Q (that is, P and Q are each completely independent sets) such that every edge connects a vertex in P to one in Q. … Read more
This is a C Program to check whether graph is DAG. A directed acyclic graph, is a directed graph which has no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex … Read more
This is a C Program to demonstrate and implement 4 color problem. The four-color theorem states that any map in a plane can be colored using four-colors in such a way that regions sharing a common boundary (other than a single point) do not share the same color. Here is source code of the C … Read more
This is a C Program to find the size of largest independent set in a given binary tree. Given a Binary Tree, find size of the Largest Independent Set(LIS) in it. A subset of all tree nodes is an independent set if there is no edge between any two nodes of the subset. For example, … Read more
This is a C Program to find hamilton cycle. Hamiltonian Path in an undirected graph is a path that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian Path such that there is an edge (in graph) from the last vertex to the first vertex of the Hamiltonian Path. Determine … Read more
This is a C Program to find feednack arc set. This is the set which contains edges which when removed from the graph, graph becomes directed acyclic graph. Here is source code of the C Program to Find a Good Feedback Edge Set in a Graph. The C program is successfully compiled and run on … Read more
This is a C Program to Implement Kadane Algorithm. Kadane algorithm is to used to obtain the maximum subarray sum from an array of integers. Here is source code of the C Program to Implement Kadane’s Algorithm. The C program is successfully compiled and run on a Linux system. The program output is also shown … Read more
This is a C Program to implement KMP algorithm for string matching. Unlike the Naive algorithm where we slide the pattern by one, we use a value from lps[] to decide the next sliding position. Let us see how we do that. When we compare pat[j] with txt[i] and see a mismatch, we know that … Read more
This is a C Program to find the size of largest independent set in a given binary tree. Given a Binary Tree, find size of the Largest Independent Set(LIS) in it. A subset of all tree nodes is an independent set if there is no edge between any two nodes of the subset. For example, … Read more
