# Questions tagged [weighted-graphs]

Questions about graphs in which every edge is associated with a weight.

328 questions
Filter by
Sorted by
Tagged with
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 ...
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/...
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
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
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
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 ...
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
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 ...
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
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
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 ...
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
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)$ ...
1 vote
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
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
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
108 views

• 21
1 vote
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 ...
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
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 ...
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 ...
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 ...
1 vote
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
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'$ ...
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
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
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
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
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 ...
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
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 ...
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
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 ...
1 vote
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
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? ...
1 vote
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 ...
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
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
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 ...
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
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 ...
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, ...