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

learn more… | top users | synonyms

1
vote
2answers
50 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 ...
7
votes
0answers
61 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
52 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
47 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
31 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
51 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 ...
4
votes
1answer
40 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 ...
2
votes
0answers
23 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 ...
2
votes
0answers
23 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 ...
3
votes
1answer
47 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 ...
0
votes
1answer
39 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 ...
0
votes
0answers
15 views

Why does Bellman-Ford with FIFO break, if node is enqued wo/ check for duplicates?

I have implemented a variation of Bellman-Ford algorithm which uses the FIFO queue to keep track of nodes whose costs might need updating. Testing it on some random graphs with no negative weights ...
3
votes
1answer
95 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
42 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
85 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 ...
2
votes
1answer
104 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
24 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
120 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
151 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
61 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 ...
8
votes
0answers
151 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
140 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$ ...
2
votes
0answers
91 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 ...
0
votes
2answers
84 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
48 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/ ...
2
votes
1answer
252 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
627 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 ...
0
votes
2answers
366 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 ...
1
vote
1answer
177 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 ...
2
votes
1answer
503 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$ ...
4
votes
1answer
58 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
26 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
140 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
18 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
41 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
219 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 ...
1
vote
1answer
313 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 ...
8
votes
2answers
2k 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 ...
0
votes
1answer
135 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 ...
1
vote
0answers
60 views

Minimal connected subgraph containing 4 specific vertecies

Let $G$ be an undirected weighted connected graph with non-negative weights on the edges, and let $v_1, v_2, v_3, v_4$ be 4 vertecies in $V[G]$. The goal: find a connected subgraph of $G$ with ...
0
votes
1answer
94 views

Reweight general weighted graph to distinct graph for using Borůvka's

Is it possible to re-weight a generally-weighted graph to a distinctly-weighted graph to apply Borůvka's algorithm (wiki) for minimum spanning tree to it? I can't seem to think of a way to make a ...
-1
votes
1answer
47 views

Limiting capacity of knapsack to a polynomial function of elements in the Knapsack problem

I saw somewhere that if we limit the capacity (weight) of the knapsack to a polynomial function of elements then the class of the problem changes to P, but it didn't say why. I can't figure out why is ...
3
votes
0answers
904 views

Applications of min spanning trees

What are the significant applications of minimum spanning trees? After doing some research online and in several textbooks, I have found three real-world applications: Building a connected network. ...
2
votes
1answer
65 views

Choice of algorithm for hierarchical clustering for minimizing network communication costs

Suppose I have a large distributed task running on a cluster system where part of the workload is compute bound and part depends on network performance. Data transfer is not completely homogeneous ...
2
votes
0answers
110 views

What is a semantic cognitive map

Based on: J. P. Carvalho, "On the Semantics and the Use of Fuzzy Cognitive Maps in Social Sciences" (WCCI, 2010 -- PDF) and Richard Dagan's web page Cognitive Mapping. A cognitive map consists of ...
5
votes
2answers
384 views

Adding a node between two others, minimizing its maximum distance to any other node

We are given an undirected graph weighted with positive arc lengths and a distinguished edge $(a,b)$ in the graph. The problem is to replace this edge by two edges $(a,c)$ and $(c,b)$ where $c$ is a ...
0
votes
2answers
1k views

Maximum length path between any two nodes in a tree with possible negative edge weights

Is there an efficient way to find the longest path between any two nodes in a tree. Given that edges can have negative weights. I know about the diameter problem which finds the longest path in a ...
0
votes
0answers
143 views

Proof of shortest-paths optimality conditions

I am struggling with understanding the proof of shortest-paths optimality conditions. Let $G$ be an edge-weighted digraph. Then values in $distTo[]$ are the shortest path distances from $s$ iff: ...
2
votes
1answer
54 views

Is traversing an unconnected graph possible?

I have been assigned a fun project: design and implement a program that maintains the data of a simple social network. Each person in the network should have a profile that contains his name, current ...
1
vote
1answer
88 views

Using Dijkstra to find shortest path in relation to two weight functions?

I'm given a graph and two weight functions, $w_1$ and $w_2$, such that there doesn't exist a negative loop in the graph in $w_1$ and $w_2$. I'm also given two vertices, $s$ and $t$, and am asked to ...