Questions tagged [weighted-graphs]
Questions about graphs in which every edge is associated with a weight.
328
questions
-1
votes
1
answer
25
views
weighted graph separation algorithm proof
I have a graph G (G=(V,E)), where each edge has a non negative weight to it.
My problem is to find a subset S (it doesn't have to exist) of nodes such the sum of all the weights of the edges that ...
0
votes
2
answers
53
views
Calculate shortest cycle that contains node $s$
Let $ G(V,E,w)$ be a graph with no negative weights.
Describe an algorithm that returns the shortest cycle containing a node $ v $.
I came across this algorithm https://courses.engr.illinois.edu/cs374/...
- 135
0
votes
1
answer
80
views
Dynamic routing algorithm
In static routing where the network parameters dont change, we can use Djikstra's or Bellman-Ford's algorithm to find the shortest path to send data from source to destination.However in dynamic ...
- 101
1
vote
1
answer
47
views
Subpath optimality lemma in weighted undirected graphs
In an introductory course on Dijkstra's algorithm, I enunciated the following lemma :
Let x →* z be a shortest path in a weighted graph and let y be any vertex along that path. It follows that x →* y ...
- 233
1
vote
1
answer
46
views
Subdivide a graph into non-crossing triangles with maximum edge weight
Let $G=(V,E)$ be a complete finite graph with the vertices arranged in a circle. Each edge has a nonnegative weight, and we would like to find an efficient algorithm to find a subgraph of maximum ...
- 293
0
votes
1
answer
42
views
Tweaking Floyd-Warshall Algorithm to detect cycles
Cheers, I am trying to solve the problem of minimum length cycle in a graph, and I came across a solution that suggested that I should tweak the Floyd-Warshall algorithm to solve that. It stated that ...
3
votes
1
answer
122
views
Is there an efficient algorithm to find GCD of all cycles' lengths in directed multigraph?
I have weighted connected directed graph with cycles which can have multiple edges and loops (edge from vertex back to itself). Weight of each edge is its length (always positive integer). There ...
- 255
0
votes
0
answers
43
views
bellman ford and dijkstra sparse vs dense graphs
I believe using big o notation that Bellman-Ford is to be expected to be faster on sparse graphs and dijkstra's should be expected to be faster on dense graphs, but in practice dijkstra's is always ...
0
votes
0
answers
25
views
Updating Shortest Path Weight from One Destination to Another
Let $G=(V,E)$ be a directed graph with possibly negative edge weights. Given a destination $t$. Suppose that we have already known $d_v$, the shortest path weight from $v$ to $t$. If I'd like to ...
- 121
1
vote
1
answer
18
views
Why do we round from 1/2 when converting the LP to ILP for the weighted vertex cover problem?
I understand that to approximate a solution to the weighted vertex cover, we need to relax the integer linear program to a linear program which can be solved in polynomial time, but why do we round ...
- 13
2
votes
0
answers
41
views
Translating weighted regular expressions with the complement operator to weighted deterministic automata
I want to implement regexp search via translation to deterministic automata, as a toy project.
TLDR: how to combine the extended regular expressions with the weighted regular expressions, with the ...
- 83
2
votes
3
answers
671
views
Determines if the minimum spanning tree only uses edges with an integer weight, when E, V are in O(n)
Given a undirected graph $G=(V,E)$ with $|V|=n$ and $|E|=2022n$ and some weight function $w\colon E\to \mathbb{R}$, and $0≤ w(e) ≤n$ for all $e∈E$,
Describe an algorithm that determines if the MST ...
- 55
2
votes
1
answer
41
views
Spanning tree that maximizes all-pairs bandwidth => Maximum spanning tree?
Let $G = (V, E)$ be a weighted, undirected graph, with $f: E \to \mathbb{R}$ its weight function. Given a path $P = (e_1, \dots, e_k)$, we call $\operatorname{bwd}(P) = \min_{1 \le i \le k} f(e_i)$ ...
- 123
1
vote
0
answers
83
views
Clash Royale Algorithm for troops path
I am making a clone of Clash Royale which is basically a Tower Defence game.
As you can see from the picture you can deploy different troops only in your side of the court (that blue rectangle), and ...
- 19
1
vote
1
answer
125
views
How to find the lightest path that has at least one vertex of each color?
I've faced this question in my homework.
In a graph $G=(V,\ E)$ where every $v\in V$ has a color, a colored path is a path such that it has at least one vertex of each color.
We're given a directed ...
- 456
1
vote
0
answers
12
views
Aggregating pairwise ratings in a graph
A finite set of individuals provide bounded non-binary pairwise ratings of other individuals (say, -10 to +10), forming a directed graph (cycles possible).
I'd like to determine aggregate ratings for ...
- 111
1
vote
1
answer
108
views
Find if an edge doesn't belong to any $MST$ with some edges of unknown weights
I've faced this problem with my homework.
We're given a weighted, undirected graph $G=(V,\ E,\ w)$ with weight function $w:E\rightarrow \mathbb{R_{\ge0}}$, someone deleted the weights of some edges $T\...
- 456
2
votes
1
answer
50
views
Flow with edge-weight restrictions
I am given a graph $G=(V,E)$ undirected and two vertices, the source vertex $s$ and the target vertex $t$. Additionally, each edge comes with a capacity $c(e)$ (non-negative) and a set of weight ...
1
vote
1
answer
22
views
Max-Min Weighted Matching
The maximum weighted matching problem (https://en.wikipedia.org/wiki/Maximum_weight_matching) finds a matching in a weighted graph that has maximum sum of weights. I was wondering if there are any ...
- 25
1
vote
0
answers
19
views
How to find if there's an MST where vertex $v$ has degree 2 in it? [duplicate]
I've faced this question and I hope that someone can help with it.
Question: We're given an undirected graph $G=(V,E,w)$ where $w\colon E\rightarrow \mathbb{Q}$ and vertex $v$. We want to find if ...
- 456
1
vote
1
answer
130
views
How to find lightest path in directed weighted graph where each edge has a color
We're Given a directed graph $G = (V, E)$ and a weight function $\omega : E \rightarrow \mathbb{Z}$. Each edge is colored with one of these colors: Red, Green, Blue. Given two vertices $s,t \in V$, ...
- 456
8
votes
11
answers
4k
views
Real life examples of *zero* weight edges in graphs
The meaning of edges with zero weight in a weighted graph questions me for a long time, and I even asked a related question previously.
Yet, when I recently read here a question on real life example ...
- 603
7
votes
0
answers
295
views
Shortest path in directed graphs with no more than $\log \log n $ negative edges
Given a directed graph $G=(V,E)$ with $|V|=n$ vertices and some weight function $w\colon E\to \mathbb{R}$,
I also know that there are at most $\log\log n$ negative weight edges in $G$, and $G$ does ...
- 55
18
votes
6
answers
3k
views
Real life examples of negative weight edges in graphs
I am unable to relate to any real life examples of negative weight edges in graphs. Distances between cities cannot be negative. Time taken to travel from one point to another cannot be negative. ...
- 317
1
vote
1
answer
78
views
Shortest walk from $u$ to $v$ through $w$
We have an undirected, weighted graph $G=(V, E)$ with two weight functions
$W_1 : E \rightarrow \mathbb{R}^{+}$ and $W_2 : E \rightarrow \mathbb{R}^{+}$
such that for every $e \in E$ we have $W_1(e) &...
- 21
1
vote
1
answer
161
views
There are n cities and m possible bidirectional roads and k temple. build roads with minimum cost such that each city has access to at least 1 temple
There are n cities and m possible roads and k temples. The cost of each road is given. Build ...
6
votes
3
answers
2k
views
Does the Minimum Spanning Tree include the TWO lowest cost edges?
Wikipedia's Minimum Spanning Tree reads:
Minimum-cost edge
If the minimum cost edge e of a graph is unique, then this edge is included in any MST.
Proof: if e was not included in the MST, removing ...
- 291
2
votes
1
answer
54
views
Is the MCP language really np hard?
I have a graph $G=\left(V , E\right)$ and source $s$ and target $t$.
I also have a weight function $w: V\rightarrow \mathbb{R^+}^k$, meaning a vertex given $k$ non negative weights.
There is an upper ...
3
votes
1
answer
26
views
On a coloring that uses $2\cdot a\left( G \right)$ colors
Denote $G=\left( V, E \right)$ arboricity by $a\left( G \right)$. I'm trying to understand why $G$ is $2\cdot a \left( G \right)$-colorable. I came across this post. Both the OP and the answer say ...
3
votes
0
answers
67
views
Coloring nodes and edges in node-weighted graph
I have a graph $G$ with $n$ nodes and $O(n)$ edges. Each of the nodes has a positive integral weight at least 2, such that sum of all weights is at most $O(n)$. We want to color the nodes and edges ...
- 156
1
vote
1
answer
36
views
Linear deterministic algorithm for finding spanning tree T with minimal maximum edge
Given an undirected connected graph $G = (V, E)$ with weights $w : $E → $R$$^+$, define for a spanning tree T the value $λ$(T) = $max_e$∈$T${w(e)} (the maximal edge weight in T ).
I need to find a ...
- 11
0
votes
1
answer
28
views
Minimum spanning tree where weights of edges are intersecting sets
Given Graph $G=(V, E)$, where each edge in $E$ is assigned a "weight" as a set of elements. $w(e) = S_e \ \forall e \in E$.
Find a subset $E' \subset E$ such that it spans $G$, i.e., $E'$ ...
0
votes
1
answer
33
views
Does the A* algorithm visit every node in an undirected graph when no path to the goal node exists?
When no path to the goalnode exists, does the A*-Algorithm a) visit and b) expand every node in an undirected graph?
I have a monotone heuristic.
Thanks
1
vote
0
answers
47
views
What if have a algorithm that could generate a NFA of 42 states of any binary string of 2^32 length?
For example, if we have a true algorithm that could generate any NFA of at most 42 states from any binary string of 2^32 length. So, this algorithm can not just recognize the string but just recreate ...
- 11
3
votes
2
answers
128
views
Given DAG $G(V,E)$, find $\forall v \in V$ the sum of the weights of vertices that are reachable from the $v$
Given a DAG $G=(V,E)$ and a weights function on the vertices $w:V \to \mathbb{R}$, suggest an algorithm that computes for every $v \in V$ the sum of the weights of vertices that are reachable from it.
...
- 203
2
votes
0
answers
53
views
Minimum unrooted binary spanning tree
Given a graph $G$ with $n$ tip vertices, $n-2$ internal vertices, and a cost on each edge $C(v)$, find a minimum spanning tree subject to degree constraints:
tips have a degree of $1$
internal ...
- 121
-2
votes
2
answers
50
views
Shortest path covering certain nodes in a graph
Consider a weighted graph where each node represents a city. Now a truck starts
from a city A and it has to cover a set of cities ...
- 1
4
votes
0
answers
57
views
Collision detection with vary constraints
I have an edge-weighted tree, and for each leaf of the tree, there's a corresponding point on the 2D plane. For each pair of points $u$ and $v$, let $d_{uv}$ be the distance of the corresponding ...
- 171
1
vote
0
answers
74
views
Find two paths in a Graph which are disjunct in
Assuming we have two trains that start in one source edge. I want to find an algorithm that finds two paths for these trains so that they won't meet in an edge at any given time. So we have the train ...
- 11
0
votes
1
answer
100
views
Prove Edited Algorithm of Bellman–Ford?
Please Note: I forgot a small detail which caused the algorithm to be incorrect, please read the new version and thanks for pointing that.
I am stuck on this question for a week and hope to get some ...
- 13
1
vote
1
answer
41
views
Polynomially Equivalent Pairs of Minimization-Maximization Problems in Weighted Graphs
I am studying computational complexity using Papadimitrious's book: "Computational Complexity". I am trying to solve Problem 9.5.14, about polynomially equivalent minimization-maximization ...
- 225
1
vote
1
answer
273
views
Sorting criteria for Kruskal's algorithm
I am studying Kruskal's algorithm. Is the only acceptable sorting criteria to sort edges from lowest weighted edge to greatest weighted edge? I ask this because I assume that if the algorithm used an ...
- 113
2
votes
2
answers
240
views
Bellman-Ford algorithm intuition
We recently learned Bellman-Ford algorithm for shortest path in class, but I didn't understand it.
Can you give me intuition for why the algorithm works? And can you please explain why it is correct? ...
- 21
1
vote
1
answer
30
views
Prune and search Algorithm for Generating a Bottleneck Spanning Tree
I'm trying to wrap my head around a prune-and-search algorithm for returning a bottleneck spanning tree, currently I'm selecting the median weight of all the edges, then divide the original graph G ...
4
votes
0
answers
55
views
Find an optimal matching in a complete graph
I have a complete edge-weighted graph with $n$ vertices (and therefore $n\cdot(n-1)/2$ edges). I want to find a complete matching (i.e., perfect matching) in which the quotient $sum_G/A_G$ is maximal, ...
- 41
1
vote
2
answers
110
views
Is the inverse of MST cut property true? Why?
If we partition the nodes of a graph into sets A and B, there is an edge e of weight larger than any other edge crossing the cut between A and B, e would never be in the minimum spanning tree?
- 37
1
vote
1
answer
71
views
Variant of assignment problem
This is something like assignment problem, we have 2 group of people, first contains $n$ person and second contains $m$ person. we have a matrix $C$ which is an $n \times m$ matrix and our goal is to ...
- 11
5
votes
1
answer
60
views
Maximum-weight set of cliques of size 3 with no common vertices in undirected graph
I'm looking for an algorithm/insight into a problem that's an extension of the Maximum Weight Matching problem. The maximum weight matching problem looks for the max-weight set of edges that contain 0 ...
- 53
2
votes
1
answer
138
views
A more rigorous proof on a Bellman-Ford's corollary
The following corollary can be found at page 653 of "Introduction to algorithms (3rd edition)"
Corollary 24.3
Let $G = (V, E)$ be a weighted, directed graph with source vertex $s$
and a ...
- 282
1
vote
2
answers
347
views
Problem to understand a Bellman Ford algorithm exercise
I am trying to understand the following exercise from Introduction to algorithm (3rd edtion).
Exercise 24.1-3 (page 654)
Given a weighted, directed graph $G=(V, E)$ with no negative-weight cycles, ...
- 282