Questions tagged [graphs]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
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 ...
1
vote
2answers
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
1
vote
0answers
17 views

ILP relaxation for Cluster deletion on C5

I'm looking for additional constraints that get rid of fractional solutions for the LP relaxation of the Cluster Deletion problem: Given an undirected graph $G = (V, E)$, find a min. sized $E' \...
2
votes
1answer
63 views

Name of BFS variant with multiple queues with different priorities

Is there a name for the following variant of BFS that operates on trees with non-root starting point?: Instead of a single queue that all neighbor nodes are added to when processing a node, two ...
1
vote
0answers
13 views

Trivial clarification with the analysis of the Dijkstra Algorithm as dealt with in Keneth Rosen's “Discrete Mathematics and its Application”

I was going through the text, "Discrete Mathematics and its Application" by Kenneth Rosen where I came across the analysis of the Dijkstra Algorithm and felt that the values at some places ...
0
votes
2answers
23 views

Doubt regarding strong component in a graph

I know that strong component in a graph means between any 2 vertices there should be bi-directional path. My doubt is cycle is always a strong component. can there be any other subgraph with some ...
0
votes
1answer
40 views

Negative cycle detection using Bellman-Ford and its correctness

I recently started studying algorithms on my own using Cormen and MIT algo videos in YouTube. I am going thru Bellman-Ford. I have 2 doubts about the correctness of the algorithm: Why are we ...
2
votes
1answer
94 views

Get every possible (connected) subgraph containing x number of nodes

If I had a graph representing the USA with each node representing a state, and each edge linking adjoining states, is there a graph algorithm that would give me every possible unique group of 4 states ...
0
votes
0answers
15 views

A request for literature on Matching your partner problem

I need reference for a good book (a title and an author will do) or reference on the web which explains the problem of matching procedures of suitable partners between several males and females based ...
0
votes
0answers
30 views

Scheduling algorithm for overlapping jobs - single resource?

I have a single resource that will need to shared for running multiple parallel jobs. Think of the resource as a straight line numbered from 1 to 100. The jobs occupy part of the line while they are ...
1
vote
1answer
31 views

Checking if two statements can be reached in one control flow

Assume I have a graph representing the control flow and the call graph of a given program. I also have a first and a second statement. I now want to figure out if it is possible to execute both ...
1
vote
1answer
67 views

how to reduce the time complexity of this code?

I have a graph G=(V,E). A list of nodes NODE subset of V. I want to find out all the ...
0
votes
1answer
55 views

Maximum Capacity Path Problem with constraints

I was trying to develop an algorithm for maximum capacity problem with constraints but couldn't figure out the necessary changes required for correct output. The problem is: Given an undirected graph ...
0
votes
1answer
52 views

How to find all paths of length up to k between two nodes in a directed graph?

Let's say I have a directed graph represented as an adjacency matrix, and I'm given two nodes $u,v$ and a parameter $k$. Let's also say that the maximal degree of a node in the graph is $d$. What is ...
1
vote
0answers
40 views

Dividing students into 4 groups based on preferences is NP-complete

Given a set of students $H$ of size $n$, and a set $E \subseteq H \times H $ of pairs of students that dislike each other, we want to determine whether it's possible to divide them into $4$ groups ...
4
votes
1answer
50 views

Marginal Probability of Generating a Tree

Fix some finite graph $G = (V, E)$, and some vertex $x$. Suppose I generate a random sub-tree of $G$ of size $N$, containing $x$, as follows: Let $T_0 = \{ x \}$. For $0 < n \leqslant N$ i. Let ...
1
vote
1answer
134 views

What's the name of this DFS variation

Classical DFS: A set of tasks with precedence constraints (saying “u must be done before v”) are given. This problem can be represented by a directed graph. We assume that the graph is acyclic. A DFS ...
1
vote
1answer
54 views

Determine whether given f is shortest path function

I have the following question: Let $G = (V,E)$ be a directed graph with a weight function $w:E\rightarrow \mathbb{R}^+$, and let $s \in V$ be a vertex such that there is a path from $v$ to every ...
0
votes
0answers
34 views

Algorithm to calculate shortest path when updating the heaviest edge in a path [duplicate]

For a given graph $G=(V,E)$ and path $p= v_1 \to v_2 \to ...\to v_k$, $w^\ast(p)$ represents the weight of the path between $v_1$ and $v_k$ excluding max_edge. $$w^\ast(p) = \sum_{i=1}^{k-1} w(v_i, v_{...
0
votes
1answer
25 views

Shortest unambiguous representation of a graph over an alphabet

I just started reading a book on theoretical computer science and here are a couple of beginner questions about graphs, which I am struggling to answer: Given the graph with the matrix ...
2
votes
1answer
115 views

Modified shortest path problem

For a given graph $G=(V,E)$ and a given weight function $W$ lets say we define the new weight for path p to be the regular weight minus the heaviest edge in that path, i.e: $w^*(p)=\varSigma(w(v_i,v_{...
0
votes
1answer
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 ?
2
votes
1answer
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 ...
2
votes
2answers
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.
0
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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'...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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: ...
2
votes
1answer
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 ...
0
votes
1answer
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 ...
36
votes
14answers
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 ...
1
vote
2answers
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 ...
0
votes
1answer
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-...
1
vote
0answers
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?
1
vote
1answer
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$ ...
0
votes
0answers
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 ...
0
votes
2answers
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 ...
5
votes
2answers
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 ...
1
vote
0answers
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,...
4
votes
1answer
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. ...
0
votes
0answers
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 ...
4
votes
2answers
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 ...
0
votes
0answers
44 views

Counting a walk $i \rightarrow k \rightarrow l \rightarrow i \rightarrow k \rightarrow j \rightarrow l \rightarrow j$ in a graph

This paper gives a procedure for counting redundant paths (which I will refer to as walks) in a graph using its adjacency matrix. As an exercise, I want to count only the walks of the form $i \...
1
vote
1answer
37 views

How to remove 'skip' edges from a DAG? (How to find only the longest path from each node to each of its sinks?)

In two separate projects, I have come across this problem and I still don't have a good solution for it, so I thought it was worth describing here. Consider the following problem: I have a set of ...

1
3 4
5
6 7
77