Questions tagged [graph-traversal]

Questions about graph traversal algorithms such as BFS and DFS.

Filter by
Sorted by
Tagged with
2 votes
1 answer
48 views

DFS (Depth-first search) vs BFS (Breadth-first search) Space Optimizations

Problem I am currently digging deep into some optimizations on the classical iterative approaches to both DFS and BFS algorithms. The material I'm currently using at my University presents both ...
Michel H's user avatar
  • 123
0 votes
1 answer
18 views

Algorithms for stacking gage blocks

I'm looking for algorithms for stacking gage blocks. For those unaware, gage blocks are used in machine shops for measuring with high precision and come in sets something like this... Mitutoyo's 56 ...
David Carpenter's user avatar
2 votes
1 answer
75 views

Graph labyrinth solving sequence

Starting from a vertex of an unknown, finite, strongly connected directed graph, we want to 'get out' (reach the vertex of the labyrinth called 'end'). Each vertex has two exits (edge which goes from ...
user555076's user avatar
1 vote
1 answer
70 views

How to find largest caterpillar in a tree

A caterpillar is a subgraph which consists of a path with at most four leaves (legs) attached to each node (but a node can also have no leaves). This is not the same as finding the longest path, ...
Stephen's user avatar
  • 11
1 vote
1 answer
27 views

Proving that Breadth-First Search (BFS) results in a bipartition of a tree

In my studies of discrete mathematics, I've learned that a tree graph is inherently bipartite. I'm interested in finding an algorithmic approach to determine its bipartition. It seems to me that ...
Ferran Gonzalez's user avatar
5 votes
3 answers
1k views

Seeking a Polynomial Time Algorithm for Balanced Weight Assignment to Nodes in a Tree

I have a tree, $T$, with $n$ nodes. My goal is to assign a non-zero weight to each node such that the following condition is met: Upon removing any arbitrary node, the total weight of nodes in each ...
Ferran Gonzalez's user avatar
0 votes
1 answer
92 views

DFS to assign guards to nodes in a tree structure

Consider a uniquely designed museum where rooms are arranged in a tree structure. Each room can have up to two child rooms connected by a path. The task is to develop an algorithm to place a minimum ...
mark's user avatar
  • 67
1 vote
0 answers
41 views

How to efficiently calculate the longest road in catan?

In Catan you can calculate the longest road by finding the longest (most roads) path which does not repeat any edges/roads, and does not cross through a vertex controlled by another player. I started ...
Bovard's user avatar
  • 111
2 votes
1 answer
261 views

Prove the relation between space complexity and time complexity of the graph search which uses "the explored set"

I was referring to the textbook Artificial Intelligence: A modern approach 3rd by Stuart Russell and Peter Norvig. what to prove about the general "graph search": (Here I assume "within ...
An5Drama's user avatar
  • 193
2 votes
1 answer
58 views

Graph containing a cycle of $2k$

Given an undirected graph $G=(V,E)$, and a parameter $k\in \mathbb{N}$ such that $k\geq 2$, how can I show that if $|E|\geq |V|^{1+\frac{1}{k}}$, a cycle $C$ exists in $G$ such that $|C|\leq 2k$? The ...
Dan D-man's user avatar
  • 514
4 votes
0 answers
146 views

Negative cycle of even length

Given an undirected graph $(V,E)$ with weights on edges $\in Z$ is it possible to find a negative cycle of even length (not the weight of the cycle, but the number of edges contained in the cycle) in ...
Bait Hoven's user avatar
1 vote
1 answer
56 views

Finding the pair of nodes with maximum distance in an arbitrary rooted tree

Suppose we are given an arbitrary rooted tree. We want to find two nodes that have the maximum distance among all pairs of nodes. I am looking for an algorithm with time complexity $\mathcal{O}(n)$, ...
Mason Rashford's user avatar
1 vote
1 answer
78 views

Running time of modified BFS algorithm to find shortest path in weighted DAG

While the shortest path can be calculated with $O(V+E)$ time over a weighted directed acyclic graph using topological sort, I wonder about the running time of the following BFS type algorithm I ...
wsz_fantasy's user avatar
1 vote
1 answer
81 views

number of edges that appeared at least in one shortest path

In a simple weighted graph, with n vertices and m edges , for each pair of vertices we want to find the number of edges that appeared at least in one of the shortest paths between these two vertices. ...
mostamele's user avatar
1 vote
1 answer
64 views

Can Dijkstra's algorithm be used this way?

Let us say that I wanted to solve a Hamiltonian path problem by treating it as a Hamiltonian cycle(on a weighted graph). I use a TSP solver, and implement a dummy node of edge weight zero, whose ...
Johnny Upman's user avatar
2 votes
2 answers
153 views

A $O(|E||V|)$ algorithm to determine if a graph is singly connected?

In exercise 22.3-13 of CLRS (Intro to Algorithms 3rd edition), the authors provide the following problem: A directed graph $G = (V, E)$ is singly connected if the existence of a path from $u$ to $v$ ...
Hugh Mann's user avatar
0 votes
1 answer
60 views

Optimizing Delivery Routes in a Graph-Based Network to Minimize Maximum Delivery Time

In a graph with N nodes, where each node represents a house and is labeled from 0 to N-1, an ...
maplemaple's user avatar
2 votes
1 answer
246 views

An efficient way to find a pair of unrelated edges

I'm writing a program which uses an undirected graph to represent certain social connections, and I'm trying to check whether or not it's contains a specific induced subgraph. Given a dense an ...
Benicio Agüero's user avatar
0 votes
0 answers
35 views

A* (A-star) search algorithm including closest distance from a node to an obstacle in heuristic and step cost

I want to include the distance of a node to the closest obstacle in the cost function, so that the path length is not only minimal, but also not near obstacles. We know that: Dijkstra's algorithm uses ...
Math98's user avatar
  • 1
0 votes
0 answers
57 views

Question about implication in proof that predecessor subgraph is a breadth-first tree

Given the following theorem and definitions from Introduction to Algorithms 3rd edition by CLRS: Theorem 22.5: (Correctness of breadth-first search) Let $G = (V, E)$ be a directed or undirected graph, ...
Hugh Mann's user avatar
0 votes
0 answers
43 views

Confusion about Lemma for Breadth-first search (BFS) proof of correctness

I'm working my way through the graph section of Introduction to Algorithms by CLRS (3E,4E) and I came across the following proof: 3E: Lemma 22.2 Let $G = (V, E)$ be a directed or undirected graph, and ...
Hugh Mann's user avatar
0 votes
1 answer
29 views

Sign confusion in a BFS lemma

I have a confusion related the Lemma 22.1 in Cormen Leiserson Rivest Stein's Introduction to Algorithm book, Here it is written that delta(s,v) <= delta(s,u) +1 ,where s,u,v are the vertices of a ...
Ibtida Bin Ahmed's user avatar
0 votes
1 answer
57 views

What is the technical name for one sided tree traversal and which algorithms are good for it?

Looking at the image from Wikipedia page for tree traversal what is the name for a traversal that follows the dashed line exactly with repeating visits to obtain: F, B, A, B, D, C, D, E, D, B, F, G, ...
MathX's user avatar
  • 103
2 votes
1 answer
99 views

Can Rural Postman Problem with arbitrary start and end be reduced to Rural Postman Problem with single depot node?

Can Rural Postman Problem with arbitrary start and end be reduced to Rural Postman Problem with single depot node? The rural postman problem is: Given a weighted MultiDiGraph $G=(V,E)$, a subset of ...
somewhere's user avatar
3 votes
1 answer
136 views

Number of "one neighbourhood" search trees in a graph

Consider the following algorithm: We are given a planar graph $G$. We initialise a set of vertices $S$ to an empty set. We randomly pick a vertex $v$ in $G$ and insert it in $S$. Now we keep including ...
Yolov4's user avatar
  • 73
0 votes
1 answer
153 views

Checking if all nodes are reachable in a oriented graph from all other nodes

I'm having a lot of troubles understanding a preparation exercise about oriented graphs: Consider the following game played on a directed graph G = (V, E) with n nodes and m edges. A pawn is ...
JayK23's user avatar
  • 103
1 vote
1 answer
64 views

Does graph traversal require stack machine?

I'm writing a graph traversal function to be used in a garbage collector. To avoid stack overflow, I used a finite state machine. Roughly, it descends into child nodes recursively to mark objects, and ...
DannyNiu's user avatar
  • 352
0 votes
0 answers
52 views

Graph Search Algorithms that are practically fast on dense graphs

I'm trying to do some research on graph search algorithms that are practically fast on relatively dense graphs. Besides the common ones like A* or Dijkstra's, what are some graph search algorithms ...
sharkeater123's user avatar
2 votes
0 answers
101 views

On definitions of graph width

Wikipedia shows graph width $k$ as the degeneracy, an ordering of the vertices $v_1,\ldots , v_k$ for which, if we orient each edge $(v_i, v_j)$ towards $i$ where $i<j$, the maximal degree is at ...
Eric_'s user avatar
  • 445
0 votes
1 answer
116 views

How to find maximum number of edge-disjoint trails of length $k$ of a directed multi-graph $G=(V,E)$ between arbitrary start and end vertices?

How to find and return the maximum number of edge-disjoint trails of equal length $k$ of a directed weighted multi-graph $G=(V,E)$ between arbitrary start and end vertices? The start and end vertices ...
IsalanOnkar's user avatar
0 votes
1 answer
37 views

Order list of lines to make them form a closed contour

I need to solve the following type of problem. I have a list of many connected lines forming a closed contour. These lines come as the output of a MarchingSquare algorithm. Consequently they are lines ...
aSpagno's user avatar
1 vote
1 answer
129 views

Finding shortest path between two points in a polygon whose vertices are given?

A contiguous single polygon is specified by it's vertices $(v_1, \ldots, v_n)$, given in order such that the line between $v_i$ and $v_{i+1}$ is an edge of the polygon (there's also an edge between $...
chausies's user avatar
  • 532
3 votes
1 answer
50 views

How to determine the largest number of disconnected arcs in a graph?

Given a directed graph $G=(V,E)$, I'm wondering if there's a way to determine the largest size of a set of edges that are disconnected pairwise. There is a similar problem for vertices (Maximum ...
underdog987's user avatar
1 vote
0 answers
607 views

Find the number of all possibilities to visit all vertices once in a connected graph

Let $G$ be a connected undirected graph, e.g.: u -- v -- w \ / x I would like to determine the number of sequences in which every vertex of the graph is ...
Bob Aiden Scott's user avatar
0 votes
2 answers
68 views

Can negative edge weights in a graph be positive numbers?

I'm a little confused by the concept of a "negative" edge weight. All of the examples I have seen represent negative edge weights as negative numbers. Is it possible for an edge weight to ...
Daniel's user avatar
  • 149
0 votes
0 answers
104 views

Prove that BFS computes the shortest path from one vertex to another

I read in Algorithms in C by Sedgewick that we can easily prove by induction that breadth-first search algorithm computes the shortest path from one vertex to another (unweighted graphs or weighted ...
hcentenaro's user avatar
0 votes
0 answers
33 views

Directed graph where each node must contain all elements from source nodes

I'm looking for a directed graph data structure where each node is unique and contains a set of elements (at least one). Each node must contain all elements from nodes pointing to it so it possible to ...
alphashock's user avatar
0 votes
1 answer
117 views

How can I track multiple shortest paths from one node to another using Dijkstra / Bellman-Ford

I want to find how many shortest paths are there from Node A to node B. For example, let's say we have a graph with 3 nodes and 3 connections: from 1 to 2 weight 5 from 1 to 3 weight 11 from 2 to 3 ...
ViktorMaksimoski's user avatar
1 vote
1 answer
84 views

How can we find a shortest closed walk passing through all vertices?

How can we find a walk with the minimal length starting from a vertex $v$, passing through all vertices and returning back to $v$? We allow vertices and edges to be repeated along the walk. The ...
licheng's user avatar
  • 365
2 votes
2 answers
87 views

Does it require O(|E|) time to visit all nodes?

In an undirected graph it takes $O(|V| + |E|)$ time to visit all nodes in a simple graph using BFS according to our lecture notes. But why can't you visit them all in $(|V|)$ time instead?
Simd's user avatar
  • 996
1 vote
1 answer
206 views

Find a weight threshold for edges for maximum number of connected components in a graph

So the problem starts with a graph in which every node is connected with every node by a weighted edge. The goal is to find a weight treshold W, so that every edge that has a weight lower than or ...
Tomyy's user avatar
  • 25
0 votes
1 answer
69 views

Correct Term for describing "diamond" subgraphs in a Directed Acyclic Graph

I am trying to research handling a specific type of possible subgraph in directed acyclic graphs. However, I am struggling to find the correct term to use. If we consider the subgraph S to be in a DAG ...
T-Tory's user avatar
  • 9
1 vote
1 answer
31 views

Route planning on line segments which can be connected or not

I have several lines that are shown in different colours, do not know which are connected to each other in advance. I want to do path planning only using these lines, i.e., route planning. If I am ...
GPrathap's user avatar
  • 111
3 votes
1 answer
161 views

Find the largest caterpillar subtree

I have a problem to solve, but I am having some issues with it... Find an algorithm with time complexity O(V+E), where V and E stand for vertices and edges respectively. The algorithm searches a tree ...
aurel1510's user avatar
0 votes
1 answer
66 views

Calculate all distances in an undirected and unweighted graph

Which algorithm do I use and how much does it cost if I have to: Calculate all distances in an undirected and unweighted graph from two sources to all nodes. I think the most appropriate algorithm is ...
emacos's user avatar
  • 121
0 votes
1 answer
91 views

Directed weighted multigraph with dynamic edges - shortest path

I need to create an implementation of a directed weighted multigraph with dynamic edges: The edges will be changing during the pathfinding, in the following way: Summary of the pathfinding: ...
discrete coder's user avatar
0 votes
1 answer
322 views

Find the shortest distance path in a weighted graph, where the weight of each edge is non-negative and less than a constant C = 500 in linear time

The problem is to find the shortest distance in a weighted graph, where the weight of each edge is non-negative and it is given that the weight of each edge is less than a constant C. For example, C = ...
Mikey's user avatar
  • 3
0 votes
1 answer
107 views

Set of all vertices in a directed tree that are within distance of strictly larger than 2

As the title says, I'm trying to solve the question where: Input: A directed tree $T = (V, E)$. Output: The maximal subset $A \subseteq V$ of vertices such that there doesn't exist any two vertices $u,...
Salty Champ's user avatar
0 votes
0 answers
36 views

The computational complexity of a variant of algorithm for the TSP (Travelling Salesman Problem)

What is the algorithm's computational complexity for a variant of the Travelling Salesman Problem, where every node must be visited at least once, meaning that a node can be visited more than once? (...
AmirHosein Adavoudi's user avatar
0 votes
1 answer
68 views

Is the traveling salesman on a map NP-hard?

It is known that the general traveling salesman problem is NP-hard. Even when the distances follow the triangle inequality. But let's take the problem very literally. There are actual cities (points) ...
Rohit Pandey's user avatar

1
2 3 4 5
10