The tag has no usage guidance.

learn more… | top users | synonyms

0
votes
1answer
28 views

Understanding Jeff Erickson's analysis of a basic tree traversal algorithm

I have trying to understand graph algorithms from scratch and I have explored various resources but the most understandable for me was these lecture notes Algorithms. The way professor teaches seems ...
1
vote
2answers
69 views

Linear-time algorithm to find an odd-length cycle in a directed graph

Problem: Give a linear-time algorithm to find an odd-length (directed) cycle in a directed graph. (Exercise 3.21 of Algorithms by S. Dasgupta, C. Papadimitriou, and U. Vazirani.) The related ...
1
vote
1answer
57 views

When to use DFS and when use BFS?

Preparing for an interview. I see two cases where each one is specially suited BFS: When you need to find shortest path between vertices (if one exists). DFS: If you need to find cycles in a ...
1
vote
1answer
44 views

How do we generate a depth-first forest from the Depth First Search?

I was trying to implement an algorithm which finds the strongly connected components (SCC's) of a directed graph. In order to find the SCC's, as the last step we need to be able to generate the ...
1
vote
1answer
32 views

Efficient algorithm for finding weakly connected components

We recently studied Tarjan's algorithm at school, which finds all strongly connected components of a given graph. I was curious however how one would find all weakly connected components (I had to ...
1
vote
1answer
47 views

Partial path known in Single source shortest path problem

I'm using the A* algorithm with a consistent heuristic on a graph to determine the shortest path. If the algorithm is exploring a node $p_1$ for which there is a existing knowledge about the optimal ...
3
votes
0answers
54 views

Tree of Despair: Collecting Data from a Tree with Multiple Types of Branching

Provided is a tree with three types of node. The structure of the tree cannot be modified and traversal of the tree is limited to querying a node for its children or its parent. The objective of the ...
3
votes
1answer
92 views

How many number of different binary trees are possible for a given postorder (or preorder) traversal

I came across the problem: What is the number of binary trees with 3 nodes which when traversed in postorder give the sequence A,B,C? Now 3 being small number I was quick to draw all possible ...
3
votes
2answers
116 views

Is the Nearest Neighbor Algorithm a valid algorithm to find a Minimum Spanning Tree?

I just wrote a program that runs the Travelling Salesman Problem using the Nearest Neighbor Algorithm. Afterwards, I started looking into Minimum Spanning Trees (MST). From my understanding: The ...
3
votes
1answer
62 views

Articulation Vertex, significance and real world usage?

This question is not about any particular algorithm to look for articulation vertices (cut vertices) in a graph but rather seeking real world applications of algorithms involving such vertices. I am ...
4
votes
1answer
46 views

Given two vertices s,t in a directed graph, is there a vertex x such that xs and xt are paths?

I am curious of knowing of an efficient algorithm for the problem: Given two vertices s,t in a directed graph, is there a vertex x such that xs and ...
1
vote
1answer
30 views

Finding Connected Components Dependent on Order?

It seems to me that the outcome of a connected components algo is dependent on the start vertex. Is this correct? Say we had the graph If we started our connected component search from the vertex ...
0
votes
1answer
57 views

Longest path in a graph with special property

I have a special graph in which I have two types of edges only, say one with type 0 and one with type 1. Now I have to find a longest path in the graph such that it starts with a vertex then follows ...
0
votes
2answers
84 views

Generate random weighted graphs representing a road network

in order to solve a DARP problem I created a Python class, that can generate random graphs. I attribute a random number to every edge which represents the cost to travel over that edge. My current ...
0
votes
1answer
67 views

Detecting all cycles in un-directed graph [duplicate]

I would like to detect all the cycles(non duplicate) in a given graph, I mean if A-B-C-A is a cycle, then A-C-B-A is a duplicate of previous one and need to be considered.I could use DFS and detect a ...
5
votes
2answers
227 views

How does DFS produce MST and All pairs shortest paths in unweighted graphs?

I was reading Application of DFS from here where I came to a statement which I cannot really understand. Would anybody mind explaining this to me. For an unweighted graph, DFS traversal of the ...
5
votes
1answer
105 views

Shortest path in a known room for a Roomba

I had an interview question once which asked for an algorithm to ensure a Roomba vacuum cleaner visited/vacuumed every "cell" in an unknown shape/size room with unknown obstacles. Depth first search ...
4
votes
1answer
62 views

Variations of Depth First Travesal

While learning depth first traversal, I realise there are two approaches that are followed. Method 1. The first one is as given in the Forouzan's book is as follows: Push the initial node onto the ...
1
vote
1answer
90 views

Update labels of a tree depending on ancestors of nodes in linear time

You are given a tree $T=(V,E)$ along with a designated root node $r \in V$.The parent of any node $v \ne r$, denoted $p(v)$, is defined to be the node adjacent to $v$ in the path from $r$ to $v$. ...
4
votes
0answers
182 views

A variant of travel salesman problem in grid graph

In this problem, a robot is moving around on a rectangular grid and try to traverse and cover the whole grid, but it can only go one direction until it hits the boundaries/obstacles or its own trace. ...
1
vote
1answer
232 views

Shortest path that visits maximum number of strongly connected components

Consider a directed graph. I need to find a path that visits maximum number of strongly connected components in that graph. If there are several such paths the desired path is the path that visits ...
1
vote
0answers
33 views

Looking for name of siblings-first-depth-second traversal order

I've had to come up with a traversal order/algorithm for a project, and I am wondering if it has a name. The requirements of the algorithm are: it visits the parent before the children. it visits ...
5
votes
1answer
108 views

Level-order traversal of a balanced tree, with no parent pointers in $\mathcal o(n)$ space

Assuming you have a balanced tree, without parent-pointers, with $n$ nodes, and a height $H = \mathcal O(\log n)$. I know you can traverse the tree in level order in $\mathcal O(n)$ time using a ...
0
votes
0answers
32 views

Shortest Path Variant (constrained max hop)

INPUT: directed non negative weighted graph, s, t, k OUTPUT: SSSP from s to t where the path has $\leq k$ vertices MY PROGRESS: ...
1
vote
2answers
164 views

Shortest path visiting all nodes in an unrooted tree

I have a tree. This tree has no particular root (free-tree). I want to find a path that visit all nodes. This path has to be the shortest possible. All edges are considered to have a distance of 1. ...
2
votes
0answers
85 views

Backward data-flow: post-order or RPO on reverse CFG?

When solving backward data-flow problems, many resources (Wikipedia and many presentations found online) recommend traversing the control-flow graph (CFG) in post-order for fastest convergence, which ...
2
votes
2answers
161 views

Algorithm for grid with obstacles and movement restriction

We are given an $n \times n$ grid with some of the squares darkened. Our goal is to move from the bottom-left to the top-right corner with the following constraints: 1) We cannot step on a darkened ...
2
votes
2answers
61 views

Directed cyclic graph with node rewards and arc costs

The problem I have seems fairly simple and I feel it must have some kind of name. I have a (directed cyclic) graph. Each node has an associated reward for visiting it, and each arc costs a certain ...
1
vote
1answer
92 views

Starting BFS at s and t

INPUT: undirected graph, s, t OUTPUT: connectivity of s and t I perform BFS on s AND t, each taking turns to make one traversal. When a vertex exists in both s and t's BFS tree, we can assume it is ...
4
votes
1answer
48 views

How would I simulate a network to explore the percolation threshold of a network connected by the knight's move?

"If we consider the squares of an infinite chess board as nodes of our graph and consider each to be connected to the other eight squares that are a knight's move away from it what is the percolation ...
0
votes
1answer
32 views

Why does a graph traversal algorithm is initialised with visited[s]←true

I just had a course on algorithm, we just started to study graph traversal. the teacher wrote analgorithm but I think there is a mistake: I'm a bit shy so I didn't asked her why so... ...
0
votes
0answers
212 views

Is the reverse postorder of a digraph's reverse the same as the postorder of the digraph?

I've been reading Sedgewick's intro to algorithms book, and he says that the reverse postorder of a digraph's reverse is not the same as the postorder of the digraph, however in both cases it seems ...
2
votes
1answer
54 views

Move tokens from s to t as fast as possible

Let $G=(V, E)$ be an unweighted and undirected graph, and $s, t \in E$. The problems starts with $n$ tokens on $s$. The goal is to move theses tokens to $t$ in a minimum of rounds with these rules ...
3
votes
0answers
53 views

Heuristics to Find Circuits Allowing for Vertex Revists

I'm currently working on a project discussing applications of the Delaunay Triangulation, and the primary use-case is applications to TSP (or relaxations of the problem). See: ...
0
votes
0answers
29 views

optimal path for traversing nodes

So here is the problem: There are n objects in a super market that you need to retrieve, then you need to go to the cashier register in the end. How do you find the best path of traversing the least ...
1
vote
0answers
41 views

Sort graph nodes by density [closed]

Imagine villages (or Internet Routers) scattered all over the world (or World Wide Web) connected by roads or shipping lanes (or Cables). All villages (nodes) has the same amount of villagers which ...
1
vote
1answer
739 views

What does pre-, post- and in-order walk mean for a n-ary tree?

The tree traversal methods explained in this Wikipedia article are pre-order, post-order and in-order. Are these methods limited to binary trees? The algorithm seems to be defined in terms of left and ...
5
votes
1answer
156 views

Unique path sums in a DAG using vertex instrumentation

I stumbled across this paper from Ball et al. In their paper they assign specific values to the edges of a graph. When the graph is traversed, or lets call it executed (since they talk about control ...
6
votes
2answers
100 views

Traversing a graph with respect to some partial order

Recently I was faced with the following Graph traversal problem: "Given an arrangement of buildings in form of a DAG. All the buildings have to be colored, but there is an order for that represented ...
0
votes
1answer
41 views

What is the order of this traversal method?

Please see below pseudo-code for finding the max-height of a b-tree ...
0
votes
1answer
55 views

Parallel shortest path in directed acyclic graphs

Finding the shortest path in a DAG is extremely easy: See the example here http://www.utdallas.edu/~sizheng/CS4349.d/l-notes.d/L17.pdf However, I cannot find a way of parallelising this code. Is ...
1
vote
2answers
140 views

Path optimization in a DAG: maximizing number of least cost arcs

I've got the following problem. I've a graph $G=(V,E)$ as in the picture and I have to calculate the optimal path from $R$ to $S$. The optimal path has to maximize the number of least cost arcs. In ...
1
vote
1answer
94 views

Path in digraph passing through given set of vertices

Suppose we have digraph G, set of its vertices W and two (possibly equal) vertices s and f. I'm looking for an algorithm which will solve the following problem: whether there is path from s to f ...
2
votes
1answer
149 views

LCA from children using bottom up approach?

I'm interested in finding the LCA of two distinct Nodes in a (not necessarily binary) tree from the bottom up without using depth. How would I go about traversing the tree, starting from any 2 ...
0
votes
1answer
55 views

How do you search a graph? [closed]

An interview question I was asked. I was first asked how to traverse a graph and next I was asked how to search one. Got the first one but not the second. What is the modern standard way to search ...
1
vote
1answer
66 views

Matching a set of paths to an incrementally generated graph

I am working on an approximate matching problem, where I have a set of paths in an unknown graph (A) and a partial graph (B), where B is generated incrementally during the matching process (and can be ...
0
votes
0answers
147 views

Failing to understand the pseudo code of the inorder traversal

Edit: Solved, see comments I don't understand how the inorder traversal traverses through the whole tree. According to wikipedia, the pseudo code for the inorder traversal is: ...
2
votes
1answer
506 views

Correctness of splitting an undirected tree into a forest of trees with even number of children

Given an undirected tree (i.e. a tree without any designated root) of even number of nodes. The task is to remove as many edges from the tree as possible to obtain a forest of trees, where each such ...
0
votes
2answers
118 views

Finding a Hamiltonian Path through the complete graph on 37 vertices: $K_{37}$ [closed]

I'm planning on making a fiber art $K_{37}$ (like the one I laser etched with help: K37: The complete graph on 37 nodes, svg). To accomplish this, the plan is to construct 37 pegs equally spaced in a ...
3
votes
3answers
152 views

Why Iterative-Deepening-DFS requires O(b*d) memory?

After reading about iterative deepening depth-first search on Wikipedia, I could understand that it just limits the depth upto which dfs can go in one iteration/call. However, I could not understand ...