# Questions tagged [graphs]

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

4,800 questions
Filter by
Sorted by
Tagged with
21 views

### Matching points on a plane with maximum total weight

I have a set of points $P = \{p_1, \dots, p_m \}, \; 0 \le m \le 10^4$ on a plane of two colors (red and green). Each point has integer x-coordinate (all x-coordinates are different), and non-negative ...
1 vote
151 views

### Question about step in proof that predecessor subgraph forms 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, ...
1 vote
38 views

### Number of maximal induced trees in a connected planar graph

An induced subgraph $G’$ of a graph $G$ is a subset of its vertices along with all the edges that are present in $G$ among those vertices. For $G’$ to be a tree, all vertices of a cycle in $G$ cannot ...
76 views

### Does there exist an algorithm / software that finds optimal graph partition while enforcing contiguity on a subgraph?

I am interested in the traditional graph partitioning problem, which roughly speaking seeks to obtain a partition of a graph into a number of components, in which each component has about the same ...
20 views

### In a directed graph, efficiently determine node reached after traveling k edges from the starting node

I am trying to solve a problem where I am given a directed graph with $n$ nodes where, from any given node, I can reach one and exactly one node. Nodes contain integers from $1$ to $n$. Starting at ...
599 views

### Find max total revenue in a directed graph

Problem: Imagine you are an agent with a knapsack, who travels a known route of cities. All cities are different: $C_1 \rightarrow C_2 \rightarrow \dots \rightarrow C_n$. Each city offers you to buy ...
1 vote
4k views

### Determine if a vertex is a part of a cycle in O(m+n) complexity

I am trying to apply BFS to the following problem, but I'm not sure how to do it Input: directed graph $G$ defined by the array of adjacency lists with n vertices and m edges, and a vertex $v$ in $G$ ...
358 views

### Algorithm : Visiting all stations in minimum time with additional constraints

I was given this question and not sure how to solve this. This is a DP minimization problem ? Problem : There are N stations in a certain region, numbered 1 through N. It takes di,j minutes to ...
39 views

### Finding min s-t cut of network with flow on the nodes

Given a network with flow on the nodes. How can we find min s-t cut in a network with flow on the nodes? We know how to find min s-t cut whenever there’s a network with flow on the edges (Ford ...
27 views

### How to understand this graph problem related to bracket sequence?

This problem comes from a competitive programming problem. I'll restate it(feel free to see it here): A balanced bracket sequence is a bracket sequence(including open and close only) of even length ...
1 vote
659 views

### Minimum distance of nodes from a set of two nodes

In an unweighted tree, suppose that we want to delete (or mark) any node which is closer to node $v$ than node $w$ ($dist(x,v) < dist(x,w)$). The solution that comes to my mind is running two BFS, ...
59 views

### About a possible optimized version of Johnson's algorithm on a DAG with "elementary circuits"

Recently I came upon the Johnson's algorithm to find "elementary circuits" on a directed graph, which is really cool to me. I'm just implementing it from scratch in C++ following the ...
21 views

### Max flow with a minimal in-degree objective on certain nodes (for edges with non-zero flow)

The following a small-scale example meant to illustrate the general problem Suppose we have $n = 60$ marbles that we want to distribute into 3 bowls, $B = \{bowl_1, bowl_2, bowl_3\}$ The marbles can ...
56 views

### Draw a flowchart of a simple payroll system that will display an employee’s information

Ask for the name of the employee. If the employee is full time, get his monthly salary rate. Then, display his name and salary. If the employee is part time, get his rate per hour and the total ...
27 views

### Minimum spanning tree using BFS

In finding a minimum spanning tree, if we use a BFS and at any node instead of deleting the edge to a repeated node, we can find the most expensive node in that cycle instead and delete it. In such a ...
936 views

### Create a binary search tree from a sorted array: Space complexity reasoning

Here is the Python code. The solution is fairly common and is seen in most textbooks like 'Cracking the Coding Interview' and 'Element of Programming Interviews'. ...
13 views

### Can Gomory-Hu tree algorithm be applied to graphs with more than one connected component?

If I have an undirected graph with more than one connected component, can I apply the Gomory-Hu algorithm directly on the entire graph or do I have to apply it separately to each component?
50 views

### What are the best parameters possible from a binary linear LDPC code where each parity-check matrix is the incidence matrix of a graph?

There is an obvious construction of linear codes from graphs, where each codeword is a cycle in the graph. Physical bits are edges in the graph, and constraints are vertices. This has been used in the ...
630 views

### Longest-Path Layering algorithm

NOTES: there are a myriad of graph data structures, I use a spin-off of a directed adjacency hash. the code provide in this post is python3 on the premise that it ...
32 views

### Why in Edmonds Karp or Ford Fulkerson Algorithm the time complexity of BFS or DFS respectively is O(E) rather than O(V+E)?

For these algorithms, the time complexity of BFS and DFS is O(E). I have gone through many websites and even the algorithm books, but I never got a clear idea of why it is O(E). It just says it's O(E) ...
14 views

### Current best output-sensitive algorithm for computing all maximal cliques of a graph

I am looking for a reference on the most optimal output-sensitive algorithm currently available for listing all maximal cliques in a graph. I know the Bron-Kerbosch algorithm is highly utilized, but ...
44 views

### Is a predecessor subgraph always connected?

Given an undirected graph $G$ with non-negative edge weights, how can we prove that the predecessor subgraph $G_{p}$ of $G$ is always connected? Here's how the predecessor subgraph is defined: for a ...
341 views

### Retrieving the cheapest path of a graph with time-dependent edge weights

There are many efficient algorithms for finding the shortest path in a network, like dijkstra's or bellman-ford's. But what if the weights of edges are time-dependent? I'm trying to find an efficient ...
1 vote
116 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 ...
1 vote
15 views

### Defining multi commodity flows as polytopes

In a multi commodity network, we define a demand to be a vector $d \in \mathbb{R}^{k}$, where $k$ is the number of pairs of sinks. That is, $k = \binom{S}{2}$, where $S$ is the set of sinks (aka ...
231 views

### Literature request: Generating all vertex subsets of a graph

I am working in an algorithm which finds a unique maximal independent set of vertices. Then, using this set, one can construct all other vertex subsets. I assume this might have some applications ...
1 vote
31 views

### Visualising pseudo-tree with two parents per node

I have an algorithm that recursively connects together pairs of nodes into new nodes. It looks like the Huffman code algorithm, except that a node can be re-used after it has been part of a merge. The ...
42 views

### Choosing root for maximum matching in tree

This question deals with how to find the maximum matching in a tree. I understood the answers, but for one part. Choose a root arbitrarily. For each subtree, calculate the maximum matching within the ...
14k views

### Retrieving the shortest path of a dynamic graph

I'm studying shortest paths in directed graphs currently. There are many efficient algorithms for finding the shortest path in a network, like dijkstra's or bellman-ford's. But what if the graph is ...
1 vote
216 views

### State-of-the-Art techniques on dynamic shortest path computations

Suppose that I would like to find the shortest path between two vertices in a dynamic graph, where the cost function of an edge changes occasionally. I understand that an efficient algorithm to target ...
1 vote
44 views

### How to compute the updated shortest paths given a set of edge insertions efficiently?

Let $G = (V, E)$ be a graph with edge weights $w: E \rightarrow \mathbb{R} \cup \{\infty\}$. Let $P := \{(a_i, b_i, w_i)\}$ be a set of tuples of nodes $a_i, b_i \in V$ with shortest distance $w_i$ ...
29 views

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 ...
174 views

### How to find an algorithm to calculate the best move for this graph based strategy game?

I'm prototyping a deterministic Risk like game. A player can move units from one node to a connected node if he has more than 1 unit the in origin node (must leave 1 unit behind). The player wins if ...
1 vote
575 views

### Scheduling problem on bipartite graph

Consider a bipartite graph $G=(U, V, E)$. Each $v \in V$ represents a soccer team, and each $u \in U$ represents a mini-tournament needs to be scheduled. If $u_i$ and $u_j$ share no common neighbor, ...
1 vote
190 views

### Unsure why (or whether?) a certain algorithm correctly computes a Minimum spanning tree

CLRS problem 23-4 part c gives an algorithm that may or may not compute a minimum spanning tree. Given some connected undirected graph G, we have ...
34 views

### Finding the smallest possible pattern order to recreate a canvas

I made this problem up in my head, and I'm looking for a solution. I realized that it's a very interesting problem, and I'm way too dumb to solve it, so I'm asking for help. The problem Given a '...
4k 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
171 views

### Prove the following claim on Hamilton Path?

I am trying to prove the following claim: Given DAG graph, there is Hamilton path iff the following algorithm returns true: Do topologic sorting. Move on the graph's vertices one by one (from low to ...
91 views

### Conditional lower bounds on the running time of the single source shortest path problem

Just out of curiosity, I was wondering whether there is a conditional lower-bound on the running time of an algorithm for the Single Source Shortest Path Problem (on directed or undirected graphs). I ...
13 views

### How to enforce convexity of triangulation output?

I implemented an incremental Delaunay triangulation algorithm. It basically works except it has this weird issue. The algorithm starts by creating a bounding triangle that it then splits recursively ...
47 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 ...
172 views

### Max flow algorithm for floating-point weights and E~=10*V

Could you, please, suggest a maximum flow algorithm for a graph with floating-point weights and the number of edges approximately equal to the number of vertices? I.e. ...
1 vote
69 views

### Find max of all trees resulting from single edge removal in generic tree in linear time

Given a generic tree with $n$ weighted nodes, there are $n-1$ edges. Removing any of the edges will partition the tree into two distinct trees, hence we can construct $2(n-1)$ possible trees in this ...
1 vote
2k views

### Updating a mst after increasing the weight of an edge in the mst

Suppose we have a weighted undirected graph $G$ and a minimum spanning tree $T$ Let $G2$ be a new graph by increasing the weight of one edge $e = (a,b)$ that is part of $T$. I'm using a common ...
111 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 ...
191 views

### Finding a cycle of length log(n) given min degree

Let $G = (V, E)$ be an undirected graph such that every $v\in V$ has $\deg(v) \geq 3$. We must create an algorithm that outputs a cycle of length O(log(n)) if it exists. This algorithm must return in ...
2k views

### CLRS Exercise 24.3-4 - Confirm Output of a Program Claiming to Implement Dijkstra's Algorithm

I'm trying to better understand Question 24.3-4 From CLRS below: Professor Gaedel has written a program that he claims implements Dijkstra’s algorithm. The program produces $v.d$ and $v.\pi$ for ...
1 vote
25 views

### Find an assignment discarding a subset of possible assignments

We have a $N \times N$ cost matrix where the cost denotes the amount incurred for assigning a worker to a task. The number of possible assignments is $N!$. Let us call this set of all possible ...
Suppose we have a bipartite graph with $N$ vertices on either side. In the full bipartite graph, the number of edges is $N^2$ and the number of possible matchings (i.e. assignments) is $N!$. Now ...