The tag has no usage guidance.

learn more… | top users | synonyms

2
votes
1answer
39 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
46 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
26 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
34 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
45 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 ...
4
votes
1answer
101 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
91 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
20 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
49 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
98 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 ...
0
votes
0answers
29 views

How to represent an improper binary tree by means of proper binary tree

By definition: a binary tree needs to fulfill 3 requirements: 1) Each node must have at most 2 children. 2) Each node must have a left and right child 3) Left children is written before the right ...
1
vote
1answer
44 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
111 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
52 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
56 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
77 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
259 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
106 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
94 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 ...
0
votes
0answers
52 views

Generalized steps to find tree traversal for any m-ary tree

So far I've read traversal techniques $(Pre-Order, In-Order, Post-Order)$ on binary trees. But In exam I've thrown up with a question, which requires me to find in-order traversal of a ternary tree. I ...
0
votes
1answer
87 views

Applying DFS algorithm to a transition system to find reachable states

Currently working on a past exam question which tells me to compute the product of two transition systems and then use DFS to find the reachable states of the product. I learnt how to compute the ...
2
votes
2answers
71 views

Difference between edges in Depth First Trees

I have a directed graph, where each node has an alphabetical value. The graph is to be traversed with topological DFS by descending alphabetical values (Z-A). The result is $M,N,P,O,Q,S,R,T$ (after ...
1
vote
1answer
87 views

Questions on Topological Sorting

Currently learning about topological sorting. My teacher gave us this problem. The answer given to us is : B,A,C,E,D,G,F,H in lexicographical order. Why does the order go from B,A,C THEN go to E ...
0
votes
0answers
114 views

Finding negative weight cycles in graph using BFS/DFS

I was learning about Bellman-Ford in CLRS and in the exercises, there is a question to find a way to list the vertices of a negative weight cycle if one exists. I was able to find one algorithm by ...
0
votes
1answer
140 views

Evaluating Statements Using a Parse Tree

I'm building a compiler. I already have a parse tree which I built using Bison for a grammar similar to the ANSI C grammar in this link. I see that for multiplicative expression in my parse tree, ...
3
votes
1answer
286 views

Algorithm to determine whether a given graph is a caterpillar tree

I am looking for an algorithm with time complexity in $\mathcal O(|V|)$ that determines whether a given graph $G=(V,E)$ is a caterpillar tree. A caterpillar tree is a tree that has a path to which ...
3
votes
1answer
98 views

Finding the minimum number of calls in a tree

I was asked this question in an interview and struggled to answer it correctly in the time allotted. Nonetheless, I thought it was an interesting problem, and I hadn't seen it before. Suppose you ...
1
vote
1answer
366 views

Binary tree traversals reversed

Am I correct in saying that traverse(node): if node is null, return print node traverse(node's right subtree) traverse(node's left subtree) would ...
0
votes
1answer
59 views

Why BFS is source vertex specific? [closed]

Take a graph $G=(V,E)$ . As we know both DFS and BFS are graph search algorithms . But why the algorithm for BFS is designed in such a way that it does not cares about the vertices that are not ...
1
vote
0answers
19 views

Satisfy edges' constraints when updating node in directed acyclical graph [closed]

I have a directed acyclical graph. Each node represents an event with start and end dates and each edge represents a constraint between to events with 2 properties: max interval between previous ...
1
vote
1answer
145 views
2
votes
2answers
136 views

Search in a partial ordering defined by tuples of numbers

This is a graph theory and partial ordering problem. Consider a set of triples {(di,ai,ci)}i=1...N, which specify edges between two nodes A and B, d denotes a departure time, a an arrival time and c a ...
4
votes
0answers
208 views

Find shortest paths in complement graph

I'm looking for an algorithm that receives as input a vertex $s$, and finds the shortest paths from $s$ to all vertices in the complement graph (undirected). The algorithm should run in $O(V+E)$ time, ...
2
votes
1answer
78 views

What is the complexity of depth first traversal that don't label nodes as discovered?

I've found an algorithm that acts like a depth first traversal that don't recognizes nodes that have been visited before. A / \ B C \ / D | E If run ...
-1
votes
1answer
64 views

Find a maximal subgraph on a tree with conditions

Given a tree, find a path on which every vertex has at most 4 leaves (can have 0 as well) and is the "biggest" (has the maximum amount of vertices possible - including the leaves). Time complexity: ...
7
votes
1answer
9k views

Algorithm to find diameter of a tree using BFS/DFS. Why does it work?

This link provides an algorithm for finding the diameter of an undirected tree using BFS/DFS. Summarizing: Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from ...
-1
votes
2answers
126 views

Edge traversals of trees [closed]

I want to find a minimal vertex in a tree from which we can traverse some edges exactly twice then come back to that vertex then do it with the rest of edges. By minimal, I mean that the difference of ...
1
vote
2answers
178 views

Applications of Depth-First Spanning Tree

I know that depth-first search can be used to produce a depth-first spanning tree, which classifies all edges as tree edges, forward edges, backward edges or cross edges. Are there any algorithms that ...
1
vote
2answers
142 views

Simple path in a graph, within a given range of lengths [closed]

Given an undirected graph $G(V,E)$ and two nodes $s$ and $t$, $s,t\in V$, find a path whose length $L$ is bounded by a lower bound $N$ and an upper bound $M$, $N\leq L\leq M$. So, for example, $N=4, ...
1
vote
1answer
169 views

What is the order of the Pancake graph in Given example & what are the properties of Pancake graph? [closed]

Pancake graph have least diameter & degree (log n/ log log n) pancake Graph with order-2 will be one single line with two nodes, labeled with permutation of node {12, 21}. pancake Graph with ...
0
votes
0answers
258 views

Hopcroft–Karp algorithm time complexity

In the last 2 paragraphs of the paper about Hopcroft–Karp algorithm to find the maximum cardinality matching in bipartite graph: https://dl.dropboxusercontent.com/u/64823035/04569670.pdf The ...
0
votes
1answer
445 views

IDDFS explained

I am trying to understand how IDDFS works by reading a wikipedia article on it. (If someone has a better literature on the subject, don't hesitate to post). Pseudocode is as follows: ...
4
votes
1answer
510 views

Finding the k-shortest path between two nodes

Given a weighted digraph $G=V,E$, and a weight function, $d(u,v)$, one can normally use Dijkstra's algorithm to obtain the shortest path. What I am interested in, is how to obtain the ...
4
votes
3answers
173 views

Algorithm to Group Vertices of Graph

Given is the following graph which is logically divided into layers (with Dijkstra's shortest paths algorithm): ...
-1
votes
1answer
360 views

Calculating the number of non-intersecting routes in an Euclidean graph

I have an Euclidean graph: each vertex is a point on the 2D plane, so the weight of each edge is the Euclidean distance between the vertices. I found a geometric proof that every optimal TSP solution ...
-1
votes
1answer
469 views

Efficient way to find intersections

I have an Euclidean graph: each vertex is a point on the 2D plane, so the weight of each edge is the Euclidean distance between the vertices. I am randomly creating a path thru all the vertices and I ...
2
votes
2answers
182 views

Prove that any directed cycle in the graph of a partial order must only involve one node

So I have the question: Prove that any directed cycle in the graph of a partial order must only involve one node. So I know that a partial order must be transitive, antisymmetric, and reflective, ...
1
vote
1answer
139 views

Converting graphs to sets of paths

I have an Euclidean, undirected graph: each vertex is a point on the 2D plane, so the weight of each edge is the Euclidean distance between the vertices. The number of vertices with no edges is ...
12
votes
2answers
1k views

Shortest non intersecting path for a graph embedded in a euclidean plane (2D)

What algorithm would you use to find the shortest path of a graph, which is embedded in an euclidean plane, such that the path should not contain any self-intersections (in the embedding)? For ...
5
votes
1answer
71 views

What is the optimal solution to prove the reachbility of a node from the root?

I have a finite automaton with these properties: Contains cycles It's a directed graph All the states/nodes are initialy reachable from the initial state It has final states but I guess it isn't ...