Questions tagged [weighted-graphs]
Questions about graphs in which every edge is associated with a weight.
309
questions
1
vote
0answers
15 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 ...
1
vote
1answer
49 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$, ...
7
votes
11answers
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 ...
7
votes
0answers
212 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 ...
18
votes
6answers
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. ...
1
vote
1answer
66 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) &...
1
vote
1answer
81 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
3answers
1k 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 ...
2
votes
1answer
49 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
1answer
25 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
0answers
63 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 ...
1
vote
1answer
30 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 ...
0
votes
1answer
25 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
1answer
26 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
0answers
41 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 ...
2
votes
2answers
80 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.
...
2
votes
0answers
31 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 degree $1$
internal vertices ...
-2
votes
2answers
44 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 ...
4
votes
0answers
52 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 ...
1
vote
0answers
64 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 ...
0
votes
1answer
85 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 ...
1
vote
1answer
35 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 ...
1
vote
1answer
172 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 ...
2
votes
2answers
158 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? ...
1
vote
1answer
24 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
0answers
54 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, ...
1
vote
2answers
82 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?
1
vote
1answer
62 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 ...
5
votes
1answer
50 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 ...
2
votes
1answer
113 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 ...
1
vote
2answers
292 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, ...
2
votes
1answer
43 views
Job Shop Problem: How do you get an ordered sequence of operations from the disjunctive acyclic graph?
Intro
The job shop problem is a classic scheduling theory problem. Given $N$ jobs and $M$ machines, a typical goal of the JSP is to minimise the makespan (starting time of the last operation + its ...
1
vote
0answers
28 views
Running time of Goldberg's densest subgraph algorithm for integer edge weighted graphs
The running time of the original non-weighted algorithm is $\mathcal{O}(M(n, n + m)\,log(n))$,
where $M(n, m)$ is the execution time for finding a min-cut in a network with $n$ nodes and $m$ edges ...
1
vote
2answers
65 views
Maximise the value of the minimum weight intra edge
I've been doing review problems for a midterm and I came across this one
problem that I haven't been able to solve. The problem essentially says
that given a complete graph $G=(V,E)$ partition the ...
1
vote
1answer
138 views
Find MST on grid graph with only weight of 1 and 2 in $O(|V|+|E|)$
Given a grid graph $G=(V,E)$ which has only two different integer costs/weights of 1 and 2. Find Minimum Spanning Tree in $O(|V|+|E|)$.
I tried the following:
Changing Kruskal using a counting Sort ...
2
votes
2answers
105 views
Find cycles with specific weights in complete graph
(this is a cross-post from mathoverflow)
Assume I have an undirected edge-weighted complete graph $G$ of $N$ nodes (every node is connected to every other node, and each edge has an associated weight)....
1
vote
0answers
33 views
Find approximate 'best' matching pairs by calculating the fewest possible weights
My specific problem is as follows:
Given two list of texts (in the order of 5 to 50 items)
Find best matching pairs with their corresponding matching score (weight)
Where each item can only be ...
1
vote
0answers
215 views
Finding s-t min-cut of undirected graph
Given an undirected graph with non-negative edge weights, and two vertices $s,t$ in the graph. I would like to find the minimal cut such that $s$ and $t$ are on different sides of the cut.
For example ...
0
votes
1answer
23 views
Distance transform with variable "impedance"
The distance transform gives the distance of each pixel in a mask to the nearest zero.
E.g. lets take the Taxicab distance transform:
...
0
votes
0answers
27 views
Cycles of a multigraph with a property on the edges
Let $n$ be a positive integer. On a circle are arranged $n$ points $A_1$, $\ldots$, $A_n$. We put some arrows from $A_1$ to $A_2$, from $A_2$ to $A_3$, etc., from $A_n$ to $A_1$. On each arrow are ...
1
vote
1answer
488 views
Is the minimum bottleneck spanning tree also a minimum spanning tree for an undirected graph with unique edge weights?
I can see a counterexample such as this:
But I can also see in some cases it could be the same. I am trying to understand what property makes a MBST also a MST?
2
votes
1answer
158 views
Detecting cycles with weight zero in a directed graph
I am given a directed graph $G=(V, E)$ with a weight function $w: E\to\mathbb{R}$, that doesn't contain negative cycles.
I need to find an algorithm that returns ...
2
votes
0answers
35 views
find zero weight cycles in a directed graph [duplicate]
I need to plan an algorithm that decides if a directed weighted graph $G = (V,E)$ has a zero weight cycle.
the graph has no negtive cycles
the algorithm needs to be in $O(|V| \cdot |E|)$ time
my ...
0
votes
0answers
106 views
What is the significance of Bellman-Ford and linear programming for scheduling and makespans?
CLRS exercise 24.4-9 says the following:
Show that the Bellman-Ford algorithm, when run on the constraint graph for a system $Ax \leq b$ of difference constraints, minimizes the quantity $\max_i\{x_i\...
0
votes
1answer
107 views
Vertices reachable from negative-weight cycles in Bellman-Ford
TLDR: I want to know if there's a simple way to fill in distances for all vertices reachable from negative weight cycles (not just ones on the cycle itself) once Bellman-Ford has found a negative-...
1
vote
1answer
98 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
...
2
votes
1answer
103 views
shortest path in color-weighted graphs
I want to find an algorithm to find the shortest path in a vertex-colored vertex-weighted graph. Every vertex with the same color has the same weight and the total weight of a path should be the sum ...
2
votes
1answer
120 views
How to define a path between two sets of vertices?
In section 17.2 of the book "Combinatorial optimization polyhedra and efficiency" by Schrijver, he describes the Hungarian method for maximum weight matching in bi-partite graphs (with ...
1
vote
1answer
29 views
Find sets of weighted objects to maximize number of sets with weight >= X
I have N objects, each of which has a weight. I need to form combinations of the objects to maximize how many sets of objects add up to at least x total weight. Combinations can consist of any number ...
1
vote
1answer
79 views
Finding an algorithm that minimizes vertex weight sum of a subgraph that satisfies several constraints
I have a vertex-weighted undirected graph $(V,E)$ with root vertices $R = {r1, ..., rn}$. I need to find the subset $V'⊂V$ such that $R⊂V'$, $N[V']=V$, $∀v'∈V '[∃r∈R ($path($r', v'$)$)]$ that ...
