The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
1answer
31 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 ...
0
votes
0answers
31 views

Sort graph nodes by density [on hold]

Cyclic connected undirected graph. Every node in a graph has T value initially zero. Suppose there is a traverse via shortest path between every two nodes which increases every node's T value it ...
4
votes
1answer
99 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
87 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
17 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
47 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
90 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
26 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
33 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
109 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
232 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
100 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
90 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
70 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
80 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
111 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
122 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
280 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
97 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
350 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
58 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
139 views
2
votes
2answers
127 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 ...
3
votes
0answers
202 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
72 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
62 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: ...
6
votes
1answer
8k 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
124 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
172 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
133 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
168 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
256 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
414 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
480 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
170 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
346 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
429 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
179 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
69 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 ...
2
votes
2answers
550 views

Minimum cost closed walk in a graph

Is there an efficient algorithm which gives the minimum cost closed walk in an undirected graph, which visits all vertices? Does this problem have a name? I tried to reduce this to similar problems ...
5
votes
1answer
184 views

Question about the formal proof of the inorder traversing

In Don Knuth's famous series of books, The Art of Computer Programming, section 2.3.1, he describes an algorithm to traverse binary tree in inorder, making use of an auxiliary stack: T1 ...
1
vote
2answers
538 views

Why is the node with the greatest DFS post-order number not necessarily a sink?

A sink in a directed graph is a node with no outgoing edges. If I perform a depth first search, why is it that the node with the least post-order number (and thus the highest pre-order number) not ...