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
5 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
2answers
43 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
32 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
0
votes
0answers
25 views
Google Line chart - Draw x-axis based on 24 hours before
I have a chart that I want to modify so the x-value only shows how the values have changed the latest 24-hours. Currently it shows all values from all dates that has been put in. Where can I modify ...
1
vote
0answers
50 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 ...
0
votes
0answers
87 views
Route planning in public transport application
I'm making a journey planner (or a general timetable application) for all the public transport in my country (bus/train/air).
The state of the project is at midpoint, now I'm having a bit of a hard ...
1
vote
3answers
80 views
How to find of what vertices is made cycle in undirected graph if there is only one cycle in graph?
how to find of what vertices is made cycle in undirected graph if there is only one cycle in graph?
I have code for finding cycle in graph, but right now I need code that will find of what vertices ...
-2
votes
1answer
38 views
Spoj Shopping wrong result
can someone give me tricky test example that crash my code. Task --> http://www.spoj.com/problems/SHOP/
I can't find any mistake in my code so I am asking your help.
Code:
...
0
votes
1answer
33 views
Pseudocode for BFS(from The Algorithm Design, 2nd Ed.) confusion?
I need help with BFS pseudocode from The Algortihm Design Manual 2nd Edition, Skiena.
Line that says process vertex u as desired
and same thing but with edge(s) process edge (u, v) as desired
How ...
2
votes
2answers
41 views
Algorithm for finding a spanning tree with weights of 1 and 2 only
Given a weighted, connected, simple undirected graph G with weights of only 1 and 2 on each edge, find the MST of G in O(V+E).
Any ideas?
Sorry for the phrasing of the question, I tried translating ...
1
vote
1answer
43 views
Python and list mutability in an all-paths algorithm
I've been working on a all-simple-paths algorithm in python based off of networkx's version. At the moment the only changes I'm trying to make are to get it to get ALL paths for ALL nodes without ...
-2
votes
0answers
26 views
How to find polygons overlap reign
I have an algorithmic problem.
I have a set of different polygons in the 2D space. Each polygon is represented according to its vertex representation (x and y coordinates) and may contain up to N ...
16
votes
1answer
359 views
What are the differences between segment trees, interval trees, binary indexed trees and range trees?
What are differences between segment trees, interval trees, binary indexed trees and range trees in terms of:
Key idea/definition
Applications
Performance/Order in higher dimensions/Space ...
1
vote
2answers
28 views
Find all crtical node sets in a graph
Given a graph , I want to find the sets S1, S2, ... of nodes whose removal may disconnect the network. Each of these sets may contain a single node or more.
Also any of these sets are not subsets of ...
1
vote
3answers
67 views
How to find the neighbors of a graph effiiciently
I have a program that create graphs as shown below
The algorithm starts at the green color node and traverses the graph. Assume that a node (Linked list type node with 4 references Left, Right, Up ...
