# Questions tagged [weighted-graphs]

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

110 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
920 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 ...
• 221
236 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 ...
• 153
447 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 ...
• 55
774 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 ...
• 161
142 views

### Negative cycle of even length

Given an undirected graph $(V,E)$ with weights on edges $\in Z$ is it possible to find a negative cycle of even length (not the weight of the cycle, but the number of edges contained in the cycle) in ...
60 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 ...
• 171
86 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, ...
• 41
386 views

### Is there a relationship between graph entropy and node entropy?

Eagle, et al [1] discuss the notion of node entropy and this is captured in igraph via the diversity metric. I was wondering if there was any relationship between these node entropies and the idea of ...
• 141
86 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 ...
186 views

### Time taken by virus to reach all nodes

Given a connected graph, with weighted edges, a virus starts from a given node. It takes x seconds for the virus to travel from a node to one of its neighbours where x is directly proportional to the ...
305 views

### Dynamic all pairs shortest path edge removal

I have a planar(|E|=O(V)) undirected graph with positive edge weights. I have already calculated all pairs shortest path with Floyd–Warshall algorithm. Now I want to recalculate APSP with an edge ...
• 131
147 views

• 222
90 views

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

Consider these two sets of coordinate pairs with weights: ...
• 131
440 views

• 41
1 vote
20 views

### finding common navigational paths / central nodes within a graph

I have a directed weighted graph representing street (edges weighted by distance) and street intersections (nodes). Using this graph, I would like find central nodes that a person might find ...
• 111
1 vote