# Questions tagged [weighted-graphs]

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

204 questions
Filter by
Sorted by
Tagged with
246 views

### Weighted Matching with multiple assignments and min assignments

I need to do a weighted matching between two sets (say students and professors). The set of students is much larger than set of professors. So multiple students can be matched to professors. However, ...
4k views

### maximum weighted path(s) in a DAG

Given a weighted directed acyclic graph (DAG), I need to find all maximum weighted paths between the start node(s), i.e. zero incoming edges, and the end node(s), i.e. zero outgoing edges. My current ...
411 views

### Rules of converting a weighted digraph to an undirected graph?

What are the rules of converting a weighted digraph to a weighted, undirected graph? I understand that the edges should go in both directions from vertex to vertex. However, do the weights of each ...
56 views

### Finding errors in weighted graphs

I have a weighted graph where each edge is a 1d vector eg if weight going from A to B is 1 then from B to A it is -1. In the graph each cycle should add to zero though sometimes the weights have ...
144 views

### Distance of a Graph node to a group of nodes?

Consider a graph where edges represent the similarity of two nodes. In general, the graph is sparse with edges existing between only similar nodes (I can achieve this by deleting edges with similarity ...
1k views

### Finding shortest paths in undirected graphs with possibly negative edge weights

The book "Algorithms" by Robert Sedgewick and Kevin Wayne hinted that (see the quote below) there are efficient algorithms for finding shortest paths in undirected graphs with possibly negative edge ...
123 views

### Bidirectional Search on possible negative weight edges digraphs

There are plenty material about bidirectional search with non-negative edge weights. One example is this paper. I am looking for any improvements using a bidirectional approach for acyclic digraphs ...
96 views

### route and/or packing optimization algorithm

What type of problem would this question fall under, are there known algorithms/heuristics for it, what would be good resources to learn more about solving it? Given: a list of items each with a ...
45 views

### Maximum One Third Cut

I want to solve the following problem (This is a homework problem. Not looking for definite or complete answers): Maximum One Third Cut: Input: An undirected graph G=(V,E) where V={1,2,...,n}, such ...
234 views

### “Combinational” Decision Graph - Cheapest search algorithm

I have a special kind of decision graph, where Multiple decisions must be made in combination, to accomplish the path. Not sure if Multiobjective or Combinational is the right term here, let me know ...
338 views

### Algorithm for finding connected components checking as few edges as possible

Is there a good algorithm to find connected components in undirected graphs with at the lowest possible costs given as the total weight of the edges being checked?
382 views

### Dijkstras Algorithm with Bounded Integer Edge Weights

I don't really understand how we can use the fact that the edge weights are integers in the range [1, 2, ... , C] in order to speed up the computation of Dijkstra's algorithm. I read this lecture but ...
480 views

### Bounded Integer Edge Weights, Dijkstra's Algorithm

I'm trying to understand how we can get the time complexity of Dijkstra's Algorithm down from O(V²) (for a matrix-implemented Dijkstra's) to O(V) if the edge weights of our graph are bounded by a ...
321 views

### Finding path that minimizes largest of the sum of weights of each group in a directed multigraph

Given a directed multigraph with $n$ groups of edges and without cycles, can we find the path that minimizes the largest of the sum of weights of each group? All weights are non-negative integers in ...
80 views

### Finding minimum spanning tree of a special form graph

I'm trying to find an efficient algorithm that will find me the minimum spanning tree of an undirected, weighted graph of this particular form: My idea was a recursive solution: Suppose the algorithm ...
985 views

### All-pairs minimax path problem - MST [closed]

Let $G(V, E)$ be an undirected weighted (positive) graph. Given a path $s-t$ find the path that minimizes the maximum weight of any of its edges. This is the minimax path problem. It is know that a ...
70 views

### Polynomial LP-based algorithm for cost minimization of DAG weights modification

Given a DAG $G=(V,E)$, with non-negative weights $w_e \, \forall e\in E$, we want to modify (increase/decrease) the weights such that: $\forall u,v\in V$ and $\forall p_1\neq p_2$ paths from $u$ to ...
1k views

### Shortest walk through a given subset of edges

Given an undirected weighted graph $G = (V, \{E,F\})$, how to find the shortest walk that passes through all edges $e \in E$ exactly once? I'd like to know if there is a general approach to this ...
128 views

### Path cover with paths of bounded length, in the plane

I have a weighted, undirected, Euclidean complete graph $G$, a special vertex $r$, and an upper bound $b$. I want to find a minimum-cost path cover that covers all vertices of $G$, subject to the ...
82 views

### Algorithm for finding the set of minimum coordinate pairs

Consider these two sets of coordinate pairs with weights: ...
431 views

### Online version of bellman-ford algorithm?

Suppose I have a graph on which I've run the Bellman-Ford algorithm. Now I change the weight of subset of edges. Is there an efficient way to re-run the algorithm without having to completely start ...
35 views

### How to choose the maximum vertices you can delete from set while atleast 1 of its neighbors is in set?

We have a graph with connections to vertices given to us. For example, consider that following pairs of vertices are connected: ...
309 views

### Understanding the Diameter Constrained MST Problem

I am interested in understanding the DCMST problem, explained in this paper (http://www.dcc.ic.uff.br/~celso/artigos/cpdcmst.pdf). I don't think I understand it as I should. Here is how I understand ...
338 views

### Complexity of shortest paths if paths have to use edges from different partitions

We are given a simple, undirected, weighted, incomplete graph $G=(V,E)$, where $V$ is the set of vertices, and $E$ is the set of edges. In addition, a collection of sets $S$ is given, which fully ...
598 views

### Diameter-constrained Minimum Spanning Tree Problem

The diameter-constrained Minimum Spanning Tree (MST) problem is as follows: you have a undirected weighted graph $G = (V,E)$ of different weights where $V$ is the set of vertices and $E$ is the set of ...
341 views

### Bhandari Algorithm: Canceling Edges

I have a quick question on implementing the Bhandari algorithm. I do not have the textbook where the algorithm is originally given (Bhandari, Ramesh (1999). Survivable networks: algorithms for ...
277 views

### Can I change the order of iteratorion in the Floyd-Warshall Algorithm?

I am studying how Floyd-Warshall works and came across this doubt. In the code: ...
835 views

### Path in directed, weighted, cyclic graph with total distance closest to D?

Input: Directed, weighted, cyclic graph G. Two distinct vertices in that graph, A and B, where there exists a path from A to B. A distance d. Output: A path between A and B with distance closest to d....
219 views

### Vehicle Routing Problem Using Simulated Annealing

Suppose I have some locations where goods are to be delivered in multiple time slots(like 7-10 am , 10 am-1 pm, time slots are continuous). All the locations are connected with each other(completely ...
851 views

### Does Dijkstra's Algorithm actually check nodes marked as visited?

I guess this is an implementation question, but I suppose it can be answered for the typical way this algorithm works. So, most ways the algorithm has been explained to me involve going from a source ...
10k views

### Is zero allowed as an edge's weight, in a weighted graph?

I am trying to write a script that generates random graphs and I need to know if an edge in a weighted graph can have the 0 value. actually it makes sense that 0 could be used as an edge's weight, ...
536 views

### Faster maximum weight matching algorithm in bipartite graph

I need to do a maximum weight matching in bipartite graphs rather than maximum weight perfect matching (which means that there is no need to match all the nodes). The nodes each side are both (at ...
16k views

### When is the minimum spanning tree for a graph not unique

Given a weighted, undirected graph G: Which conditions must hold true so that there are multiple minimum spanning trees for G? I know that the MST is unique when all of the weights are distinct, but ...
77 views

### I know the algorithms, but i still don't know how to approach the questions

I study Graphs Analysis by myself and i understood most of the material just fine. But, there is one huge problem with my approach that prevents me from solving tests. I don't know how to build new ...
712 views

### Is is possible compute the max flow with max cost through an instance of maxflow-mincost?

I have a flow network with gains. In practical terms, a gain is the opposite of a cost. So, I interested in finding the maximal gain of a network flow, what could be interpreted as finding a maximum ...
202 views

### Maximize cost in graph with variable costs

Consider the following problem. A prisoner eats once a day, he can either have a low, or a high calorie dish. In order to be allowed to eat the high calorie dish, he must not have eaten the previous ...
162 views

### Maximum weighted antichain over a DAG with cardinality constraint

Let $G=(V,E)$ be a vertex weighted DAG (Directed Acyclic Graph), with positive real valued weights. Let also $k\leq \left\vert V\right\vert$, is there any way to find a maximum weighted antichain ...
228 views

### Equivalent definition of minimal spanning tree

Prove that $T$ is MST $\Leftrightarrow$ for any edge $uv \notin T$, $uv$ has the maximal weight on the cycle created by adding $uv$ to $T$. It's my attempt to prove $\Rightarrow$: Consider the cycle ...
503 views

### Optimal meeting point in directed graph

Let $G(V, E)$ be a edge-weighted directed connected graph and $v_1, \dots, v_n \in V$ be some vertices. Let $d(a, b)$ denote the length of the shortest path from $a$ to $b$, for $a,b \in V$. I need ...
1k views

### Simple Way to Convert an Adjacency Matrix to a CSR Graph and Vice Versa

Let's say for the following weighted, undirected graph: I am given the adjacency matrix A[5][5]: ...
85 views

### Partial path known in Single source shortest path problem

I'm using the A* algorithm with a consistent heuristic on a graph to determine the shortest path. If the algorithm is exploring a node $p_1$ for which there is a existing knowledge about the optimal ...
454 views

### Why can't we run Bellman Ford from the source and relax edges out from the neighbours recursively and do a single pass through the edges?

At each $k$ th iteration of BF, we can are guaranteed to have computed the shortest paths that are at most $k$ long. That makes perfect sense me. If we relax a set of edges $k$ times, then we for sure ...
5k views

### Why do we have different algorithm for MST when graphs are directed?

What was the reason to come up with Chu–Liu/Edmonds' algorithm when the input graph is directed instead of using the Prim's or Krushkal's method for finding Minimum spanning tree ? What cases are not ...
45 views

Let $G = (Q, \Delta, W)$ be a finite weighted graph with $\Delta: Q \times Q$ and $W: Q \times Q \to \mathbb{R}^{+}$. Is it the case that there always exist a function $W': Q \times Q \to \mathbb{Q}^{+... 0answers 24 views ### Maximum Weight Planarization of Size$n$[duplicate] Problem: Maximum Weight Planarization Given a weighted non-planar graph with$n$vertices, and$m = \mathcal O\left(n^2\right)$edges. Find the subgraph with$n$nodes (but possibly removing edges to ... 0answers 40 views ### Bus stops problem I have the following problem I need to solve, and I hope you can point me to the right direction. I have a bunch (4000) of people addresses in a city that are mapped to coordinates (longitude and ... 2answers 1k views ### Counting Minimum Spanning Trees I understand how Kruskal's algorithm works. However, I am not sure how to determine the number of minimum spanning trees that a given graph has. For example say graph$G=(V,E)$given by When running ... 1answer 96 views ### On deterministic weighted graph isomorphism from randomized Is there a$O(n^2)$algorithm to resolve isomorphism between two weighted$n$-vertex graphs? This is a much easier problem than graph isomorphism. Basically take an real edge weight set$\{w_1,\dots,...
I am aware of using Bellman-Ford on a graph $G=(V,E)$ with no negative cycles to find the single-source single-destination shortest paths from source $s$ to target $t$ (both in $V$) using at most $k$ ...