# Questions tagged [graphs]

Questions about graphs, discrete structures of nodes which are connected by edges, including trees and graphs with weighted edges.

4,497 questions
Filter by
Sorted by
Tagged with
16 views

### How to find a crticial edge in a flow network?

The complete question is as follows: An edge of a flow network is called critical if decreasing the capacity of this edge results in a decrease in the maximum flow. Give an efficient algorithm that ...
19 views

### Algorithms for finding closest graph node within set of nodes

Given a set of nodes $N$ on an undirected, weighted graph $G$ and a query node $n$, what is the fastest algorithm for finding the node in $N$ that is closest to $n$? Furthermore, say we are doing many ...
1 vote
42 views

### Data structure and optimal algorithm for modeling reachable outputs given a set of inputs

Given the following: A set of input types $I$ = {a, b, d, ...} A set of functions $F$ (With associated costs, and possibly identical signatures) = {($c_1$, a -> d), ($c_2$, (a,b) -> e), ($c_3$, ...
33 views

### Longest shortest path between two classes of nodes

(larger context at the end) My view of the problem I have an undirected graph whose nodes can be categorized into three classes depending on some metadata (I have a function that can tell me the class ...
14 views

### Is there an algorithm able to finding the best cost in a graph that is weighted on both vertices and edges?

I have a problem that consists of finding a good solution for a graph that has vertex weights (and this cost is the highest priority), but also has edge costs.
1 vote
36 views

### What algorithm will visit each node in a graph a number of times equal to the number of paths to that node from the root?

First Few Iterations of the Algorithm We have an algorithm in which a squirrel visits the nodes of a directed graph. Our graph has two colors of edges: black and white. Initially, the graph has black ...
33 views

### Algorithm for maximum non-crossing edge set in bipartite graph with a fixed permutation

I'm trying to identify an algorithm to solve this computational problem Input: Bipartite graph (V, W, E), with E ⊆ V×W A fixed ...
28 views

### Does a minimum spanning tree necessarily provide the lowest cost path between any 2 nodes?

If I'm given a minimum spanning tree, my understanding is that it is a structure that connects all nodes to each other through some path, and that the overall weight of the tree is smallest. However, ...
61 views

### Using topological sort to find inconsistencies represented by cycles in directed graphs

Consider the following scenario. Let $x_1,...,x_n$ be a group of cars that all drive from some point A to some point B. Each car starts driving in index order. i.e. $x_1$ starts driving strictly ...
54 views

68 views

### Efficient algorithm to count number of intersections of n sets

I've come across this problem when working on a personal project of mine. I need an efficient algorithm of counting the number of overlaps between all pair combinations of n sets. Example: Set a = [...
1 vote
21 views

### safe edge theorem proof clarification

I found the following proof for the theorem that states "A light edge that crosses a cut that respects A is safe for A": See: https://www2.hawaii.edu/~janst/311_f19/Notes/Topic-17.html ...
36 views

### Recursively deleting spanning forest from graph, how many iterations maximum to get to the empty graph?

As in the question stated, I am interested in the approximation factor of the greedy approach to compute the arboricity of the graph. My intuition tells me the factor should not be bigger than $2$, ...