All Questions
Tagged with algorithm graph-theory
3,687
questions
0
votes
0
answers
7
views
Traverse a graph with multiple stops from a starting point? [duplicate]
I have an undirected weighted graph I need to traverse from X node to a list of nodes. The list is unordered by default, meaning that the order of which nodes are traversed is not important. What's ...
- 1
2
votes
0
answers
52
views
Neigbor-sum graph coloring algorithm
I've been able to generate a Python program that generates a sigma labelling of a graph. A sigma coloring is a vertex-coloring $f: V(G) \Rightarrow \mathbb{N}$ such that the color sums of the ...
- 21
2
votes
1
answer
47
views
Struggling with Shortest Path Calculation in Graph with Special Edge Weights
I've been working on a problem where I need to find the shortest path in a graph considering two types of edge weights: normal and special. Check Problem Here.
I have constructed an adjacency list and ...
- 23
-1
votes
0
answers
66
views
How to determine if a node in graph is connected to another node efficiently? [closed]
Now I know some people will suggest DFS or BFS etc etc, but I am looking for other faster approaches. The graph I'm working on has "mixed" directions - some edges are directed but some aren'...
- 66
2
votes
3
answers
84
views
Find number of redundant edges in components of a graph
I'm trying to solve problem 1319 on Leetcode, which is as follows:
There are n computers numbered from 0 to n - 1 connected by ethernet cables connections forming a network where connections[i] = [ai,...
- 11.6k
5
votes
1
answer
108
views
Minimal path on weighted tree query
Given a weighted tree with n vertices. there are q queries and for each query, you are given integers (u,k). find number of vertices v such that the smallest edge on the route from u to v is equal to ...
4
votes
2
answers
269
views
Minimum edges to form path with length L
I came across this problem.
Given a weighted tree T, find the minimum number of edges to form a simple path (no duplicate vertices or edges) of weight (sum of weights of edges) exactly L.
More ...
- 148
2
votes
2
answers
97
views
Linear time algorithm for computing radius of membership hyper-sphere
We are given a Graph, G(V, E), where V is the node set and E is the edge set consisting of ordered tuples (u, v). The graph is undirected, as such, if (u,v) is in E, then (v, u) is in E.
Alongside the ...
- 542
3
votes
3
answers
235
views
How to find all simple paths of no more than k lengths starting at a vertex in a directed graph?
I am trying to find all simple paths up to a given length, and working on using BFS to solve this problem. However, I am not sure about the specific algorithm to use. It seems that BFS cannot easily ...
- 55
1
vote
0
answers
83
views
Maximum Sum of Vertices in DAG Excluding Directly Connected Vertices
How can I calculate the maximum possible sum of vertices in a weighted DAG excluding vertices directly connected by an edge? This is a vertex selection problem where each vertex has a weight.
In this ...
- 195
0
votes
1
answer
46
views
Spanning disjoint trees in directed bipartite graphs
Assume we have a directed bipartite graph G with two partitions, A and B. All the edges are assumed to start from A and end in B . Assume that every vertex has at least one adjacent edge. I want to ...
- 1
4
votes
1
answer
97
views
How to calculate the length of cycles in a graph using parallel algorithms in C?
I am getting desprite, because I can't solve this problem. I hope this is the right place to ask for help in this context.
The Problem is, that I have a graph that is the union of disjoint directed ...
- 41
1
vote
1
answer
38
views
How do I run the Bipartite Matching and Min Vertex Cover Algorithms on this graph?
Hi, so I am supposed to run the Bipartite Matching and Min. vertex cover Algorithms on this graph (with s = 0 and t = 6) using Ford-Fulkerson and DFS/BFS, "breaking ties in favor of the smaller ...
- 67
0
votes
1
answer
74
views
Tarjan Algorithms for SCC
I am stumbled at this part of SCC. I know that 5,6,7 is a strongly connected component. Performing the tarjan Algorithm for SCC starting at no
de 5, I get unsatisfied values of low-link at 7.
Graph ...
2
votes
0
answers
43
views
How to implement an A* algorithm in an unknown maze?
I’m working on a project involving the A* algorithm to navigate through an unknown maze. The maze is randomly generated with walls, and the goal is to reach a specific target node. However, I’m ...
- 21