# Questions tagged [graphs]

Questions about graphs, discrete structures of nodes which are connected by edges. Popular flavors are trees and networks with edge capacity.

3,848 questions
Filter by
Sorted by
Tagged with
76 views

### Clarification in the proof for the Bellamn-Ford algorithm

While proving the correctness of the Bellman-Ford algorithm, we prove the following lemma: After k (k >= 0) iterations of relaxations, for any node u that has at least one path from s (the start ...
95 views

### Finding the shortest path in a grid which has walls

The problem is that you want to travel from the top left corner of a grid to the bottom right corner (You are initially at the top left corner). Now, there are some walls in some cells, and you have a ...
37 views

### Reducing 3-coloring problem to trio representatives

A group of students is divided into trios - groups of 3 members. Each student can be assigned to more than more trio. We want to assign their representatives, by choosing exactly one member of each ...
19 views

### Number of referee nodes required in distributed leader election algorithm

I know the reason as to why $O(\sqrt{n\log n})$ referee nodes are required. What I don't understand is how to arrive at that value, when I have $7\log n$ candidate nodes. Please forgive me if this is ...
17 views

39 views

### Graph theory : Trees

I need to determine all the trees on 25 vertices for which there exists an integer m ≥ 2, such that the degree of each vertex gives the same remainder when divided by m. Can somebody help ?
43 views

### Find a list of actions that result in desired state

I have a problem that I need to solve, and I'm looking for which area of computer science (algorithms. etc) would be appropriate to solve this problem. In the system we have a list of actions that a ...
300 views

### Chromatic number of a graph with $10$ vertices each of degree $8$?

I have simple graph G on 10 vertices the degree of each vertex is 8. I need to determine the chromatic number of G. I tried drawing and all but it seems there is a trick needs to be used.
22 views

### Could this be used to find the largest path in a graph?

Savitch's theorem "test[s] the existence of a path from a vertex s to another vertex t that uses at most ...
52 views

### Does an algorithm exist that transforms any connected graph, cyclic or not, into tree form?

I developed an algorithm that transforms any simple connected graph, cyclic or not, into a tree. The resulting tree is syntax-preserving, in a sense that it allows to reconstruct the original input ...
26 views

### Can Stoer-Wagner find min s-t cut for given s and t?

Stoer-Wagner algorithm can be used to find global minimum cut in a graph. I'm wondering if it could be adapted to find a minimum s-t cut, given s and t. We can start a single phase with {s} but there'...
18 views

### Some Problem To Understand Petri Nets for detect deadlock in 2PL Locking

hi i read a paper and some section it's not clear for me please help me to understand it.. paper topic: A Deadlock Prevention Algorithm for The TwoPhase Locking Protocol Based on Petri Net basic ...
19 views

### Minimum spanning tree with small set of possible edge weights

Given a undirected graph which only has two different edge weights $x$ and $y$ is it possible to make a faster algorithm than Prim's algorithm or Kruskal's algorithm? I saw on Kruskal's algorithm ...
24 views

### Unique-neighbor expander

I want to solve Problem 4.10 from Randomness by Salil Vadhan. https://people.seas.harvard.edu/~salil/cs225/spring15/PS3.pdf Consider a bipartite expander $G$ with left degree $D$ so that every subset ...
24 views

### A version of TSP where there is a probability each node is visited?

A friend in industry proposed a problem to me. If you have a supply warehouse, you can treat each station with products as a node. Each node has a probability it will be visited by an employee working ...
12 views

### How to get started with multi-level pairwise combinations

Let's say we have 4 ranks: 1-4 Every rank has a set of unique nodes, each pair of same-rank nodes can be combined to create a node of a rank 1 level higher, in any number of combinations: ...
200 views

### Determine whether removing a node on a graph will disconnect the graph [duplicate]

I have an undirected unweighted graph with a single component. I want to know if removing a given node will disconnect the graph. I know that I can remove the edges to the node and then use DFS to get ...
80 views

### MST - algorithm to add an edge to the graph

I have some difficulty proving the correctness of my solution to the following exercise. Let $G = (V,E)$ undirected connected graph, $w \colon E \to \mathbb{R}$ weight function. Let $T$ a MST (minimum ...
6k views

### What are some real world applications of graphs?

Can you give some real world examples of what graphs algorithms people are actually using in applications? Given a complicated graphs, say social networks, what properties/quantity people want to ...
81 views

### Detect cycles of odd total weight in a graph with {0,1}-weighted edges

Given an edge-weighted digraph $G = (V, E \subseteq V^2, w \in E \to \{0, 1\})$, is there an algorithm that returns TRUE if there is a cycle in this graph whose ...
105 views

### Number of minimum cuts in a graph

Situation : I started watching Algorithm Lectures from Stanford University (Corsera). I stuck on one video lecture(https://www.coursera.org/lecture/algorithms-divide-conquer/counting-minimum-cuts-...
28 views

### Remove vertices to get k-connected components

In a graph, I need to remove some vertices in order to get at least k-connected components. The no. of removed vertices should be low. Is there a heuristic that I could follow for this?
24 views

### BFS for transforming one word to another

I'm having a hard time understand the reasoning in the solution of 18.7 in Elements of programming interviews (EPI): Let $s$ and $t$ be stings and $D$ a dictionary, i.e., a set of strings. Define $s$ ...
23 views

### BFS Tree of a complete graph

Can somebody explain the characteristics for a BFS Tree from a complete graph?. Thanks in advance. I would need the shape of the tree, explain me a little bit how the algorithm would work in this ...
46 views

### Will the minimum spanning tree not have only those edges specified by the cycle property? [duplicate]

I have just started to understand the "Minimum Spanning Trees" (MSTs), and had come across the cycle property. I am referring to the book - Algorithm Design by Jon Kleinberg and Eva Tardos. The ...
112 views

### Algorithm design: find any path in an undirected acyclic graph which has a total sum of the nodes as a specific value

The question was asked in an interview, and I'm not sure if this is the most optimized answer, but here goes- You have an undirected acyclic graph, where each node has a non-negative value ...
32 views

### Finding weight/value of each person on a team [closed]

If I have a team, with between $n_1$ and $n_2$ people per team, with results of team's head to head matchups, how would I be able to estimate each person's value? Example data (I drew this up quickly,...
167 views

### Prove finding k disjoint paths from n given paths in a directed graph is NP-complete

Problem: Given n paths in a directed graph G(V, E) and an integer k, find out k paths among them such that no two of them pass through a common node. Prove that the given problem is in NP-complete. ...
21 views

### how to determine the optimal value of k for constructing the k-nearest neighbor graph?

I want to build a non-oriented k-nearest neighbor graph for use in a clustering method (unsupervised learning). The nodes of the graph correspond to points defined in a multidimensional real space and ...
465 views

### Find the shortest path that goes through an even number of red edges

I'm looking for an algorithm for the problem: "Given an undirected graph with positive weights on its edges and some of the edges are red and some are blue. Describe an algorithm that finds the ...