Questions tagged [weighted-graphs]

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

Filter by
Sorted by
Tagged with
-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 ...
user avatar
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/...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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)$ ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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\...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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$, ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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. ...
user avatar
  • 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) &...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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'$ ...
user avatar
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
user avatar
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 ...
user avatar
  • 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. ...
user avatar
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 ...
user avatar
-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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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? ...
user avatar
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 ...
user avatar
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, ...
user avatar
  • 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?
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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, ...
user avatar

1
2 3 4 5
7