Graph Algorithms are a sequence of well-defined steps that will solve a problem related to Graph Theory, where a Graph in this context is a collection of vertices ("nodes") and edges that connect these vertices.
0
votes
0answers
9 views
Exercise 24.4-8 in Introduction to Algorithm. It's not homework. I'm studying the book myself
Let Ax<=b be a system of m difference constraints in n unknowns. Show that the Bellman-Ford algorithm, when run on the corresponding constraint graph, maximizes sum(Xi) subject to Ax<=b and ...
0
votes
1answer
12 views
Making a fully connected graph using a distance metric
Say I have a series of several thousand nodes. For each pair of nodes I have a distance metric. This distance metric could be a physical distance ( say x,y coordinates for every node ) or other things ...
1
vote
1answer
30 views
Optimal pairs of farthest points
I have a even set of points in 2D. I need an algorithm that can make pairs of those points such that total sum of distance between pairs is maximum.
Dynamic Programming, greedy approach won't work, I ...
0
votes
0answers
8 views
merging social media profiles (Locality Sensitive Hashing)
Was wondering if anyone had any nice reading material regarding the topic which is pretty self explanatory what I want to do is create a program which is able to merge different social media profiles ...
0
votes
0answers
28 views
ByteLandian Tours
I was trying to solve a problem on hackerrank which seem not so hard because the max score is 44. I kept getting Time Exceeded on bigger test cases. Would someone take a look at it and give some ...
-1
votes
1answer
55 views
solving min-cut graph using Krager's algorithm in C#
public class Graph
{
public Graph()
{
Vertices = new Dictionary<int, List<int>>();
}
public Dictionary<int,List<int>> Vertices { get; set; }
...
0
votes
0answers
19 views
Dijkstra - My way
I've struggled a bit with Dijkstras algorithm. I'm 99% sure I've got it now. I'm posting the code, to get some feedback. After all, i'm still pretty new to this, so I want to learn as much of the ...
0
votes
1answer
23 views
Solving unbounded knapsack with A*
I'm trying to reconcile two seemingly contradictory ideas:
The unbounded knapsack optimization problem is known to be NP-hard
My colleague and I think we can solve a minor variation on it in ...
1
vote
1answer
39 views
Markov Clustering
I have two questions to be precise. Firstly, I would like to know if there is an easy way to adapt the Markov Clustering Algorithm so that I can specify in advance, how many clusters I would like to ...
0
votes
3answers
60 views
Given a directed graph, find out whether there is a route between two nodes
I'm trying to solve this problem and i'm fairly new to graphs.
I tried BFS to figure this out but i'm not getting the right answer.
What am i doing wrong? Also, is there a better way of doing this, ...
1
vote
0answers
29 views
Split graph into two parts according to min-cut between s and t vertices
I am implementing min-cut graph clustering, and I need to be able to split a
graph into two parts S and T according to the st min-cut I build on each clustering step for some s and t vertices. ...
0
votes
0answers
14 views
Time complexity of hyper graph matching related to VF2 subgraph isomorphism
I find that time complexity of VF2 is O(V^2) in the best case and O(V!·V) in the worst case, where V is number of node. So comparing two undirected garaph G with 3 nodes {1,3,4}, the V is 3.
Now I ...
-1
votes
1answer
57 views
How to efficient extract new polygons form the exist polygons
the polygons image
All of the polygons are simply, there are no holes in them.
board polygon(P0 to P7)
Red polygon (R0 to R6)
Green polygon (G0 G1 P2 G3)
Yellow polygon(Y0 to Y3)
I want to ...
1
vote
0answers
40 views
detecting general pattern of local maxima in 1D Java array
I am trying to make a simple pitch detection application for an Android phone. I have gotten the phone to display a graph of the autocorrelation values I have computed, which are stored in a one ...
android
1
vote
0answers
52 views
What algorithms do you know for beltway reconstruction?
I've faced the beltway reconstruction problem and I've developed a simple backtrack algorithm, what algorithms do you know for this problem?
Beltway Reconstruction Problem:
Assume there is a set of ...
