Questions tagged [weighted-graphs]

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

Filter by
Sorted by
Tagged with
2
votes
0answers
410 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 ...
1
vote
0answers
355 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: ...
3
votes
3answers
913 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....
0
votes
1answer
225 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 ...
0
votes
2answers
1k 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 ...
59
votes
5answers
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, ...
5
votes
0answers
592 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 ...
22
votes
3answers
20k 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 ...
0
votes
1answer
78 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 ...
0
votes
0answers
840 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 ...
0
votes
1answer
214 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 ...
1
vote
0answers
171 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 ...
1
vote
2answers
321 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 ...
12
votes
0answers
546 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 ...
0
votes
0answers
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]: ...
1
vote
1answer
88 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 ...
3
votes
1answer
494 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 ...
3
votes
1answer
6k 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 ...
5
votes
1answer
46 views

Can we always reduce the weights of a weighted graph to rationals and preserve equality relationships?

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}^{+...
2
votes
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 ...
2
votes
0answers
43 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 ...
2
votes
2answers
2k 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 ...
0
votes
1answer
99 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,...
3
votes
1answer
2k views

Dijkstra's algorithm to compute shortest paths using k edges?

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$ ...
0
votes
1answer
236 views

Edge-connectivity of a weighted undirected graph

My question consists of two parts. Let say the edge connectivity of a graph is K. I would like to change the edge connectivity value to L (> K). What is the best possible way to do so? My guess: ...
0
votes
2answers
993 views

Generate random weighted graphs representing a road network

in order to solve a DARP problem I created a Python class, that can generate random graphs. I attribute a random number to every edge which represents the cost to travel over that edge. My current ...
1
vote
1answer
255 views

What is a weighted or probabilistic automaton?

I'm developing a program that has some entities (things) that are "classified" according to "relevancy". Sort of like search engine (think PageRank). Therefore, I'm looking to implement an automaton, ...
1
vote
0answers
86 views

Branch clustering for an MST

I am working in image segmentation with super pixels. My data is a large matrix describing various attributes of each stick of pixels (such as height, width and disparity). The data comes from an ...
4
votes
1answer
1k views

All pairwise shortest paths in a graph: does knowing the path weights help?

This question concerns the all-pairs shortest paths (APSP) problem (where we are given a graph with edge $(i,j)$ given weight $w_{i,j}$ by the distances between the two nodes $i$ and $j$, and where we ...
6
votes
2answers
707 views

How to impose Euclidean distance constraint in a constraint satisfaction problem without quadratic constraints?

Best reference I could find is this one. However, I could not quite understand this one since there is no numerical example. What I am trying to achieve with one sentence How can I answer the ...
2
votes
2answers
316 views

Directed cyclic graph with node rewards and arc costs

The problem I have seems fairly simple and I feel it must have some kind of name. I have a (directed cyclic) graph. Each node has an associated reward for visiting it, and each arc costs a certain ...
10
votes
0answers
208 views

Minimum edge deletion partitioning of a planar graph

I'm interested in the time complexity of the following problem: Given an undirected planar graph $G=(V,E)$ and a weight function $w:E \rightarrow \mathbb{Z}$ (so weights can be negative, too), color ...
2
votes
1answer
714 views

Improve minimum spanning tree with new edge, with better running time than O(|V|)?

The problem gives a MST $T$ and a series of $Q$ queries, each one with a new edge $e = \{u,v\}$ such that no edge between $u$ and $v$ exists in $T$. For every query, we have to improve $T$ with $e$ ...
3
votes
0answers
413 views

Assigning edge weights under shortest path constraints

We are given a graph $G = (V,E)$ and we need to find an assignment of non-negative edge weights (You must give every edge a non-negative weight). We are also given a set $R\subseteq V$ and mapping $c_{...
0
votes
2answers
538 views

Existence of shortest path in a graph with no negative cycles?

Suppose that the input graph $G$ does not have any negative cycles but however it is permitted to contain edges having negative weight. Let $s$ be the source vertex. How do I prove that for every ...
1
vote
1answer
82 views

Removing edges of a weighted graph

I have an edge weighted $N{\times}N$ graph and the edge similarity values are bound to $[0,1]$. What I am trying to do is to find a cut-off threshold below which I can say that that edges are noisy/ ...
3
votes
1answer
2k views

SimRank on a weighted directed graph (how to calculate node similarity)

I have a weighted directed graph (it's sparse, 35,000 nodes and 19 million edges) and would like to calculate similarity scores for pairs of nodes. SimRank would be ideal for this purpose, except that ...
1
vote
1answer
3k views

Computing the k shortest edge-disjoint paths on a weighted graph

Looking for k shortest paths that do not share edges. i.e if the paths were represented as sets of edges, their intersection has to be empty. We could use Dijkstra to find the 1st "disjoint" (edge ...
1
vote
2answers
2k views

Why is T not a minimum spanning tree of G?

The Problem: Let T be a tree constructed by Dijkstra's algorithm in the process of solving the single source shortest-paths problem for a weighted connected graph G.    a. True of false:...
1
vote
1answer
2k views

How to draw a graph to disprove this statement?

The Problem: Indicate whether the following statements are true or false: a. If e is a minimum-weight edge in a connected weighted graph, it must be among edges of at least one minimum ...
7
votes
2answers
5k views

Updating an MST $T$ when the weight of an edge not in $T$ is decreased

Given an undirected, connected, weighted graph $G = (V,E,w)$ where $w$ is the weight function $w: E \to \mathbb{R}$ and a minimum spanning tree (MST) $T$ of $G$. Now we decrease the weight by $k$ of ...
4
votes
1answer
61 views

How are graph representations containing only (i, j) instead of both (i, j) and (j, i) named?

When working with undirected graph algorithms using an adjacency-list type structure, it's sometimes enough to store a given edge (i, j) just stored in the list of ...
-1
votes
1answer
33 views

Checking a property of all of the cycles in a graph

Suppose $G= (V,E)$ is a directed graph with weights on the edges. I would like to check if $G$ has the following property: if $C \subset E$ is the set of edges in a cycle of length at least $3$, then ...
1
vote
2answers
435 views

Path optimization in a DAG: maximizing number of least cost arcs

I've got the following problem. I've a graph $G=(V,E)$ as in the picture and I have to calculate the optimal path from $R$ to $S$. The optimal path has to maximize the number of least cost arcs. In ...
1
vote
0answers
23 views

Finding next lightest path [duplicate]

Using Dijkstra algorithm, how can I find the next shortest path in a directed weighted graph? (When saying next, I mean that the next path must be heavier than the lightest path and not equal). The ...
3
votes
1answer
110 views

Seemingly non sequitur in proof

I'm trying to understand a small proof in an article about computing lumpability on Markov chains. There is a small detail that I cannot understand, i.e. I don't think it follows from the argument. ...
2
votes
2answers
2k views

Covering a graph with non-overlapping cliques

I have a problem where I need to split a graph into subgraphs. The conditions for the splitting is as follows: Every subgraph must be a complete graph/clique No vertex can be part of two or more ...
2
votes
1answer
1k views

Proof for variation of Prim's and Kruskal's to find maximum-weight acyclic subgraph

I have been scratching my head to find good counter examples to the following problem: Suppose we are given a directed graph G=(V,E) in which every edge has a distinct positive edge weight. A ...
9
votes
2answers
3k views

What are Markov chains?

I'm currently reading some papers about Markov chain lumping and I'm failing to see the difference between a Markov chain and a plain directed weighted graph. For example in the article Optimal state-...
0
votes
1answer
931 views

Is it possible to convert a graph with one negative capacity to a graph with only positive capacities?

I am interested in whether a graph (say, a complete graph) with one capacity negative (or many, but one should suffice) can be reconstructed as a graph with all non-negative capacities where the max ...