Questions tagged [graph-traversal]
Questions about graph traversal algorithms such as BFS and DFS.
1
vote
0answers
32 views
$n$ machines, $n$ types of jobs with $q_j$ jobs, minimizing the cost
I have this problem
A firm has $q_j$ jobs of type $j$, where $1 \leq j \leq n$. It also has $[n] = {1,2,...n}$ machines. Machine $i$ can service any job of type $j$ where $j ≤ i$. The cost of ...
8
votes
0answers
129 views
Steps that guarantee exiting a maze
Given a 2-dimensional maze where you can give 4 commands "move up/down/right/left". Knowing the maze but not where the person is, how to find the minimum sequence of commands that guarantees exiting ...
1
vote
1answer
24 views
Shortest path in graph by flipping binary colored nodes to one color [closed]
Given a graph consists of two-colored nodes(e.g. white and black) and a starting node, and every time you visit a node, its color is switched(from black to white, or, white to black), how to find the ...
1
vote
1answer
40 views
How to perform local search to find maximal induced subgraphs?
I'm looking for efficient ways to perform local search to find maximal induced subgraphs that satisfy certain properties : a tree, a forest or a bipartite subgraph for example.
What I mean by local ...
1
vote
0answers
26 views
Order of Traversal in Bidirectional Dataflow Analysis
Does order of traversing CFG matter in solving bidirectional dataflow problems, from a performance perspective?
0
votes
2answers
52 views
Quick and space-efficient way to find whether two sets intersect
I hope you can help me -
Given a lot of sets containing integers,
I'd like for any two sets, to quickly (i.e. O(1)) ask whether they intersect.
Note that I don'...
3
votes
2answers
47 views
When searching graphs breadth-first and depth-first color the graph. Who un-colors the graph when the search is completed?
The depth-first and breadth-first algorithms for traversing graphs use a flag (or color) to mark nodes when they are visited. For example some forms of the algorithms use white/grey/black as colors. ...
3
votes
2answers
58 views
The complexity of the reachability-coreachability analysis of a finite state machine
Let $A = \{\Sigma,Q,\delta,q_{0}, Q_{m}\}$ be a finite state machine (FSM). A state $q \in Q$ is reachable if there exists a string $s \in \Sigma^{*}$ such that $\delta(q_{0},s) = q$. The state $q$ is ...
0
votes
2answers
36 views
“Process functions” in iterative and recursive depth-first search
I was reading The Algorithm Design Manual by Steven Skiena, and I noticed his use of "process functions" in depth-first search and breadth-first search. Consider the following pseudocode for depth-...
5
votes
1answer
56 views
Least number of guesses needed to determine all unknown subsets of a set
Say I have a set $\mathbb{S}=\{1,2,...,n\}$. I have an adversary who breaks up $\mathbb{S}$ into $k$ unknown and disjoint subsets. Denote this new set $\mathbb{A}$. I can guess any combination $s$ and ...
2
votes
1answer
50 views
Shortest path with a start vertex that touches all nodes at least once with repeats allowed
I tried looking this problem up for quite a bit now, but can't seem to find a whole lot of discussion about this. At first it sounded like the TSP to me, but I don't think so (it's much harder to do I ...
2
votes
2answers
77 views
Reduce the total internal border of a set of touching rectangles (using graphs)
I have a set of touching rectangles (Initial problem), and an associated graph relating the rectangles through the edges. I want to reduce the rectangles through graph operations to the minimum ...
0
votes
2answers
122 views
Minimum Distance Spanning Tree Dijkstra
I would like to construct a Minimum Distance Spanning Tree (Dijkstra) for the graph below:
MDST: {(a,c), (c,h), (c,f), (a,d), (h,g), (a,b), (d,e), (h,j), (h,i), (j,k), (e,m), (i,l)}
Is my ...
1
vote
0answers
45 views
Enumerate all re-convergent paths in a digraph (with cycles)
I'm looking for an algorithm to count and enumerate (separately, if differing complexity) all the reconvergent pathsets in a simple, directed, non-weighted graph, which may contain cycles. That is, ...
1
vote
1answer
81 views
DFS & BFS Spanning Trees
I want to construct a DFS and a BFS spanning trees for the graph below. The root is node a. At each step the next edge to be traversed should be the cheapest one.
DFS:
My understanding that to the ...
0
votes
2answers
43 views
How to traverse a graph in reverse with dfs
So I'm watching Stanford's algorithm lectures and I'm on Kosaraju's algorithm. In the lecture, the algorthm was given in 3 steps: calculate the graph with all arcs reversed, run dfs on reversed graph, ...
2
votes
2answers
76 views
Proof for BFS and DFS equivalence
I'm trying to prove (by induction) that BFS in equivalent to DFS, in the sense that they return the same set of visited nodes, but I'm stuck in the middle of some of the cases.
Let $G$ be a directed ...
1
vote
1answer
41 views
proof that BFS remains total after adding edge to graph
I'm trying to prove that if $G$ is a connected graph, then $BFS(u\in G)$ is total (i.e. it visits all the vertices of $G$).
The inductive proof consists in 2 cases:
(i) Prove that $\rm{BFS}$$(u \in \...
1
vote
1answer
58 views
Post numbers in DFS tree of an undirected graph
How could you prove:
An edge (u,v) is part of an undirected graph G. If post(u) $<$ post(v) (i.e. the post number of u is smaller than that of v) then it implies that v is an ancestor of u in the ...
1
vote
2answers
172 views
Is there a name for this graph search strategy?
The standard implementation of breadth-first search looks like
...
0
votes
2answers
33 views
Calculation of Inorder Traversal Complexity
I want to analyze complexity of traversing a BST. I directly thought that its complexity as $O(2^n)$ because there are two recursive cases. I mean $T(n) = constants + 2T(n-1)$. However, AFAI research ...
3
votes
1answer
80 views
Understanding the “ordering of the four types of edges” in DFS
The following is Exercise 22.3-6 from CLRS (Introduction to Algorithms, the 3rd edition; Page 611).
Show that in an undirected graph, classifying an edge $(u,v)$ as a tree edge or a back edge ...
0
votes
0answers
12 views
Alternative technologies/theories for a “Git for Structured Graph Databases”
Along the lines of detect differences between tree structures, I'm wondering if there are any general techniques or tools (e.g. the techniques behind the tools) that can essentially do what Git does ...
2
votes
1answer
35 views
Graph Traversal Solutions for “Find all unique paths” Problem
I was studying the grid problem where a robot is at the top left position and wants to go to the bottom right position and you need to return the number of unique paths it can take to get there with ...
0
votes
0answers
146 views
A longest path can be found using DFS
The following is a Yes/No question. In an undirected unweighted graph $G$, a longest path between two given
vertices $s$ and $t$ can be found using Depth-first search?
If it is possible to use DFS
...
0
votes
1answer
71 views
DFS on reversed graph
I was watching a lecture on determining the strongly connected components of a graph using Kosaraju's algorithm and the lecturer claimed one can easily walk the edges in reverse fashion.
While I see ...
2
votes
2answers
482 views
Proving Postorder Traversal's Time Complexity
I am looking at the following algorithm for performing a Postorder Traversal of a binary tree
...
3
votes
1answer
272 views
Tarjan's SCC : example showing necessity of lowlink definition and calculation rule?
Several questions (1, 2) have been asked about this topic already but I am trying to be more specific.
In Tarjan's SCC algorithm, the calculation of lowlink when encountering a vertex which is ...
2
votes
2answers
101 views
What is the name of a rooted tree whose nodes may have edges to their descendants?
A tree is a special kind a graph.
However, I came across a data structure which is a like a rooted tree, but where nodes are authorized to have direct links to any of their descendants. Shortcuts if ...
1
vote
1answer
46 views
Finding a minimum weight path with certain restrictions
I have a directed weighted multigraph whose vertices are sets of URLs.
We add to this multigraph all edges of the form $i\to j$ where $i\subset j$ (such edges are of zero weight), where $i$, $j$ are ...
0
votes
1answer
83 views
Conditions for a node to be a leaf node on DFS tree
Question:
Consider the DFS tree generated by a DFS on a connected graph. Write below the necessary and sufficient condition for a node v to be a leaf node on the DFS tree. The condition must be in ...
4
votes
1answer
27 views
How to identify named points by coordinates?
The problem:
This is a reduced version of a problem I currently have. I have a list of edges as input. This list contains the names of 2 nodes (the edge connects these 2 nodes) and 2 x 2D coordinates (...
1
vote
1answer
69 views
Split graph in two parts, such that most nodes have even number of edges
We have given graph of at most $200$ nodes, we want to split the given graph in two parts, such that the number of nodes with even number of edges is maximized, note that the edges that are between ...
1
vote
1answer
36 views
Breadth First Search actually require specifically Queue instead of any other type of Collection?
As far as I know, Breadth-First-Search [BFS] theory traditionally requires a Queue to process a given level of a graph (i.e: wiki seems to assume so).
But does BFS really actually require a Queue, ...
2
votes
2answers
59 views
How to graph search a LTL-generated Buchi automaton to generate valid execution paths
I have a set of tasks, and a LTL specification that describes which orders of the tasks are legal. I want to find a way to enumerate all permutations of the tasks that meet the specification.
For ...
0
votes
0answers
41 views
How many roots are there in an undirected root
Given an undirected tree with 7 nodes how many roots would this tree have. My intuition tells me that because the tree is undirected it would either be 7 or 0. How would I solve this?
1
vote
1answer
46 views
Ordering the incident edges of each vertex to have a specified pre-order traversal
Input: You are given a graph $G(V, E)$ undirected, loop-less, no parallel edges, etc. and a label function $L: V \to \mathbb{N}$. Also, a sequence of $|V|$ natural numbers is given.
Output: Is it ...
2
votes
2answers
113 views
Find out an algorithm that finds out if an undirected graph contains even length cycle or not using BFS?
I know how to find odd length cycles(a bipartite graph cannot have odd cycles) but I cannot manage to make an algorithm when considering even length cycles.
1
vote
1answer
91 views
When to terminate search for path in an infinite grid
I'm learning shortest path algorithms like Dijkstra's, BFS, etc. I understand on a 2D finite grid there are boundary conditions (i.e. size of the grid) that help terminate the algorithm and keep it in ...
1
vote
1answer
164 views
Different topologically sorted order based on DFS vertex ordering
The algorithm for topological sort, in CLRS goes as follows :
call DFS(G) to compute finishing times v.f for each vertex v
as each vertex is finished, insert it onto the front of a linked list
return ...
0
votes
0answers
29 views
How to Compute Lowpt(v) in a DFS Tree, where Lowpt(v)={w| there exist a back_edge xw, such that x is a descendant of v}?
In computing Triconnected components of a graph using HopCropt and Tarjan algorithm, i.e https://sci-hub.tw/https://epubs.siam.org/doi/pdf/10.1137/0202012, they compute two additional values Lowpt1 ...
0
votes
0answers
48 views
Single source shortest Path Algorithm in dynamic graph
In case of dynamic graphs where edges are added only (all edges have positive weight).
Goal: to keep track of the shortest path from the source to the goal node.
Are their any specific conditions ...
2
votes
1answer
36 views
Is it possible to detect a simple negative-weight cycle of weight $N$ in polynomial time?
Given a directed graph and an integer $N$, is it possible to detect a simple negative-weight cycle whose edges sum to $N$ in polynomial time? I thought about modifying the Floyd-Warshall algorithm to ...
1
vote
1answer
15 views
How to get initial flow for TSP with missing edges
I need to solve a version of the traveling salesman problem with missing edges. I've decided to use simulated annealing.
How do I generate a valid initial path effectively?
I would use a greedy ...
0
votes
0answers
62 views
v.lowlink = min(v.lowlink, w.index) line in Tarjan Algorithm
Following the pseudo-code notation used in wikipedia.
I understand the basics of the algorithm but I don't really understand this line.
When exactly is it relevant? I only found one example, and it ...
0
votes
0answers
13 views
Finding a path between 2 points passing through N points
Given a graph/plane with N points each at a given coordinate how could I find a path between 2 points via N other points where each point is weighted on how likely it is to be passed through.
...
1
vote
1answer
92 views
Understanding time complexity of a while loop that will look over all vertices and edges
I need a little clarification on differing time complexities. My analysis for the below algorithm was $O(n +nm)$, but the correct analysis would be $O(n+m)$. I know that ...
0
votes
1answer
182 views
Removing vertices that belong to a given set from a graph
If I'm given a graph $G$ with the set of vertices $V$ and a set $B \subseteq V$, can I remove all the vertices $\in B$ from $G$, as well as all edges that connect any other vertex to a vertex $\in B$ ...
2
votes
0answers
263 views
How to traverse a graph in reverse dfs order
For kosaraju's algorithm to traverse the graph in reverse order the naive solution is to reconstruct the original input graph in reverse order and dfs on it. Is there any way I can avoid creating ...
0
votes
0answers
137 views
Longest-Path Layering algorithm
NOTES:
there are a myriad of graph data structures, I use a spin-off of a directed adjacency hash.
the code provide in this post is python3 on the premise that it ...
