Questions tagged [weighted-graphs]
Questions about graphs in which every edge is associated with a weight.
362
questions
0
votes
0
answers
26
views
Finding min s-t cut of network with flow on the nodes
Given a network with flow on the nodes. How can we find min s-t cut in a network with flow on the nodes?
We know how to find min s-t cut whenever there’s a network with flow on the edges (Ford ...
0
votes
0
answers
35
views
Running time of variant of Dijkstra's algorithm
Consider the problem of finding the shortest-path distances from an origin vertex to all other vertices in a digraph. Normally in Dijkstra's algorithm, we visit the vertex whose shortest distance from ...
- 287
0
votes
1
answer
26
views
Bipartite matching with constraints on one part
We have a bipartite graph with parts $A$ and $B$, and it is edge weighted. We have some constraints for part $B$. Each constraint is in this format: Between vertices $b_1$ and $b_2$ both from part $B$,...
1
vote
0
answers
25
views
What is the name of this extension of the maximum independent set problem?
Problem: we have an undirected graph. Each vertex $v$ has a weight of $w_v$. For each vertex $v$, a nonnegative number $a_v$ is given, and for each edge $e$, a nonnegative number $b_e$ is given. ...
1
vote
0
answers
57
views
What is the name of this matching problem?
We have a bipartite graph consisting of parts $A$ and $B$. Each vertex $i$ of part $A$ has weight $w_i$ and capacity $c_i$. We say a vertex $i$ in part $A$ is satisfied if at least $c_i$ adjacent ...
3
votes
1
answer
69
views
Path planning on 2D grid graph to maximize the neighboring grid points of a path: Can we do better than brute DFS?
On a finite 4-connected grid graph, given the source point and destination, it is allowed to consecutively move in one of the four orientions (up, down, left or right) to form a path. We get 1 bonus ...
- 31
1
vote
1
answer
83
views
Can Rural Postman Problem with arbitrary start and end be reduced to Rural Postman Problem with single depot node?
Can Rural Postman Problem with arbitrary start and end be reduced to Rural Postman Problem with single depot node?
The rural postman problem is:
Given a weighted MultiDiGraph $G=(V,E)$, a subset of ...
- 11
0
votes
1
answer
96
views
How to find maximum number of edge-disjoint trails of length $k$ of a directed multi-graph $G=(V,E)$ between arbitrary start and end vertices?
How to find and return the maximum number of edge-disjoint trails of equal length $k$ of a directed weighted multi-graph $G=(V,E)$ between arbitrary start and end vertices? The start and end vertices ...
- 11
4
votes
2
answers
61
views
Single Source Shortest Path Problem with Multiple Weights Each Edge
I am trying to solve the single source shortest path problem, but with the added constraint that there is an additional weight on each edge (so we have two weights in total for each edge, call them p ...
- 149
0
votes
2
answers
55
views
Can negative edge weights in a graph be positive numbers?
I'm a little confused by the concept of a "negative" edge weight. All of the examples I have seen represent negative edge weights as negative numbers. Is it possible for an edge weight to ...
- 149
0
votes
1
answer
29
views
How can I track multiple shortest paths from one node to another using Dijkstra / Bellman-Ford
I want to find how many shortest paths are there from Node A to node B.
For example, let's say we have a graph with 3 nodes and 3 connections:
from 1 to 2 weight 5
from 1 to 3 weight 11
from 2 to 3 ...
0
votes
0
answers
20
views
Solving a weighted minimum dominating set problem with its unweighted counterpart?
Question
Is it possible to find a solution to the weighted minimum dominating set problem, by solving a (related), unweighted minimum dominating set?
Elaboration
In essence, can one convert a ...
- 123
1
vote
1
answer
116
views
Find a weight threshold for edges for maximum number of connected components in a graph
So the problem starts with a graph in which every node is connected with every node by a weighted edge. The goal is to find a weight treshold W, so that every edge that has a weight lower than or ...
- 25
0
votes
0
answers
31
views
Minimum k-cut with equally weighted sets
I've got a weighted graph $G$, where additionally each vertex has a weight too. For a fixed, given $k$ I am looking for an algorithm to partition $G$ into $k$ disjoint sets of vertices, so that:
The ...
- 1
1
vote
0
answers
87
views
Topological sort of DAG that minimizes maximum number of unique-source-edges crossing through any node when placed in 1-d line
Consider a DAG such as one shown below:
How do I find a particular topological order of nodes, such that when the nodes are placed in a straight line, the maximum number of unique-edges that cross ...
- 280
0
votes
1
answer
37
views
Which algorithm solves the single-pair shortest path in a weighted directed cyclic graph?
I need to find the shortest path between two nodes in a directed, positively weighted graph that migt contain cycles. All weights are either zero or one. If it was not weighted, I'd use breadth-first ...
- 3
0
votes
1
answer
69
views
Directed weighted multigraph with dynamic edges - shortest path
I need to create an implementation of a directed weighted multigraph with dynamic edges:
The edges will be changing during the pathfinding, in the following way:
Summary of the pathfinding:
...
0
votes
1
answer
152
views
Find the shortest distance path in a weighted graph, where the weight of each edge is non-negative and less than a constant C = 500 in linear time
The problem is to find the shortest distance in a weighted graph, where the weight of each edge is non-negative and it is given that the weight of each edge is less than a constant C. For example, C = ...
- 3
0
votes
1
answer
73
views
find the shortest path between two vertices with Dijkstra (Increase and deacrese wieght one by one)
We have a weighted and undirected graph.
I want to find the shortest path between two vertices with Dijkstra algorithm.
But in the path, the weight of the edges should be increased and decreased one ...
- 1
1
vote
1
answer
185
views
Why Prim algorithm may fail to return minimum spanning forest on disconnected undirected graph
I am trying to address the following claim- "running prim algorithm on a disconnected undirected graph returns minimum spanning forest".
I thing that the claim may be false (i.e there might ...
- 25
0
votes
1
answer
55
views
Transforming a Travelling Salesman Problem to a Maximum Clique Problem
Say you have a directed graph consisting of n nodes and containing edge weights. A starting node is also given. You want to begin your route at that node and visit each other node in the graph exactly ...
- 1
0
votes
1
answer
33
views
How sparsity term in loss function for sparse autoencoder is making hidden units inactive?
I am working on a Sparse Autoencoder but Andrew NG's notes are hard to understand.
My question is about the following equation: Loss Function.
In sparse autoencoder, the goal is to inactive some ...
-1
votes
1
answer
253
views
How to show that any greedy algorithm gives a 2-approximation for the best min weighted vertex cover
The problem I am trying to solve is that there is an underlying undirected graph G = (V, E) with weights on the vertices, where the weight on vertex ...
- 25
1
vote
3
answers
122
views
Algorithm to find Minimal Spanning Subgraph
I'm attempting to solve this problem:
Given an undirected connected graph $G=(V,E)$ with $\mathrm{weight}(e)>0$ for all $e \in E$, and a subset $S \subseteq V$, we define that a sub-graph $H=(V',E')...
- 315
0
votes
0
answers
23
views
Analyzing Parallel Matching Algorithm - Why it takes O(n+m) time and work?
Using the algorithm provided by this paper, they said that:
The algorithm defines a single phase of the local max algorithm. Each step of the phase takes at most O(log(m + n)) = O(logn) time and O(n +...
1
vote
2
answers
64
views
Shortest path algorithm on graphs with non-numerical weights
TL;DR: Floyd-Warshall algorithm seems to also accept "is-a" and "has-a" relationships as edge weights. I want to know exactly why this is fine, and how to generalize this notion of ...
1
vote
0
answers
97
views
Longest (weight-wise) walk In a directed graph with weights becoming negative after traversing once
Problem definition
I have a directed graph $G = (V,E)$, with positive weights $w(e)>0\:s.t\:\forall e \in E$
I would like to find the longest walk (i.e. edges and nodes may be repeated) in terms ...
- 11
0
votes
2
answers
56
views
MInimum Spanning Tree and Combinatorics
I just got a small confusion here,
I have a graph for which i need to get number of minimum spanning tree,
So, in graph i have 3 edges with weight 2 and 4 edges with weight 3,
in such a way that AE = ...
0
votes
2
answers
174
views
subtract the weight of the largest edge
I have an oriented and weighted graph, and I need to find the cheapest route from source to destination.
Now I have a source node A and a destination node B the cheapest path is given to me by the sum ...
- 13
2
votes
1
answer
125
views
Minimize max subtree weight among spanning trees
Suppose we have an undirected, connected graph $G$ where vertices have positive integer weights. Let $\bar{v}$ be a given vertex in $G$. Take a spanning tree $T$ of $G$ rooted at $\bar{v}$ and define ...
- 287
0
votes
1
answer
110
views
Algorithms for finding closest graph node within set of nodes
Given a set of nodes $N$ on an undirected, weighted graph $G$ and a query node $n$, what is the fastest algorithm for finding the node in $N$ that is closest to $n$?
Furthermore, say we are doing many ...
-1
votes
1
answer
35
views
Is there an algorithm able to finding the best cost in a graph that is weighted on both vertices and edges?
I have a problem that consists of finding a good solution for a graph that has vertex weights (and this cost is the highest priority), but also has edge costs.
- 1
-1
votes
1
answer
92
views
Does a minimum spanning tree necessarily provide the lowest cost path between any 2 nodes?
If I'm given a minimum spanning tree, my understanding is that it is a structure that connects all nodes to each other through some path, and that the overall weight of the tree is smallest. However, ...
- 125
3
votes
1
answer
102
views
Efficiently determine which nodes should leave a graph while maintaining connectedness
Suppose I have a graph with node weights, where a weight is either -1 or a positive integer. For example:
If a node has weight -1, it is "happy", and cannot be kicked out of the graph.
If a ...
- 133
-1
votes
1
answer
31
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
302
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/...
- 232
0
votes
1
answer
129
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
133
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
73
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 ...
- 313
0
votes
1
answer
239
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
323
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 ...
- 275
0
votes
0
answers
241
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
36
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
48
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
72
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 ...
- 201
2
votes
3
answers
1k
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
150
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
196
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
379
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 ...
- 453
1
vote
0
answers
17
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