Questions tagged [weighted-graphs]

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

203 questions
Filter by
Sorted by
Tagged with
248 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, ...
85 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 ...
945 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 ...
556 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 ...
282 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 ...
206 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 ...
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$ ...