A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

# Questions tagged [weighted-graphs]

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

66 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
525 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 ...
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 ...
565 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 ...
360 views

### graph signal processing

What's the intuition behind a ''Graph fourier transform'' ? I'm not so much interested in mathematical details or technical applications. I'm trying to grasp what a graph fourier transform actually ...
354 views

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

Eagle, et al  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 ...
26 views

81 views

### Assign weights to the edges in a DAG so that, for all S and T, all paths from S to T have equal weight

I have a DAG, and on each edge, I have a minimum and maximum weight. I would like to assign (or determine it's impossible to assign) exact weights to each edge so that Each edge's weight is between ...
121 views

4k 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. ...
57 views

### Matching of two weighted graphs allowing one-to-many mapping

I am looking for a heuristic for a graph matching problem as follows. Given two graphs: $A$ (consisting of nodes $a_i$) and $B$ (consisting of nodes $b_i$). Typically the size of $B$ is larger than ...
96 views

### Shortest path between any origin to any destination through some way stations

How can one find the shortest path between any one of the origins to any one of the destinations through a number of way stations on the way using Dijkstra algorithm? You can visit those way stations ...
208 views

### Finding negative cycle using Bellman Ford

Given a graph with |V| vertexes and |E| edges, I have to find a negative cycle, if there is one, in a graph. The wanted complexity is O(|V|*|E|). I was thinking about using Bellman-Ford to solve the ...
182 views

### Maximum number of not overlapping cycles in an undirected graph

Basically, when given an Undirected graph, the problem of getting maximum cycles is known. This case is quite different. The graphs I'm dealing with are made by converting geometric polygons to ...
462 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 ...
388 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 ...
42 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 ...
291 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 ...
147 views

### Multicommodity shortest path problem on a directed acyclic graph

I have n commodities with each a unique source and sink node. Each source-sink pair is connected in some manner on a directed acyclic graph. All arc weights are non-negative. The goal is to find the ...
31 views

### Ordering vertices of graph based on specific vertex-transitivity

Given any complete directed weighted graph $G$ with $n$ vertices and matrix of non-unique weights $W$, find a weak ordering $T(G, W)$ on the vertices of the graph satisfying the following conditions: ...
13 views

### complexity of computing fractional edge-chromatic number of an edge-weighted graph

Let $(G,w)$ be an edge-weighted graph, where the weights $w(e)$ are assumed to be rational. My question is: What is the complexity of computing $\chi'_f(G,w)$, the fractional edge-chromatic number of ...
68 views

### Approporiate algorithm for a graph theory problem

So I have recently ran into a graph theory problem and was unable to find a matching algorithm for the problem or reword the problem to match some existing algorithm. The problem is pretty ...
286 views

### Given a binary tree of leaves with weights, find minimum weights for internal nodes (such that sum(weighti-weightj) is minimized for (i,j)∈E(T))

So this is a question within a bigger question for which I've reduced to this so far: If I have a tree (phylogenetic) with known weights for leaves, how would I find the weights for all internal ...
52 views

### Calculate maximum sum of nodes property with limit on distance being traversed between nodes in a given graph

Given is an undirected weighted graph with N nodes, with each node having a property/Value. Aim is to find the bestpath which maximizes the sum of the nodes property which can be visited given a ...
173 views

### How to handle negative edge weights in distance vector routing protocol with a digraph?

In a Distance Vector routing protocol each node implements a Bellman-Ford inspired algorithm that shares it's routing table (Distance Vector) with each of it's incoming links (upstream neighbors). ...
79 views

### Prove an algorithm. Give directed graph edge weights such that weight of every cycle is 0

I need to construct a graph with the following properties: $w(u, v)$ = $-w(v, u)$, for every edge $(u, v) \in E$ Weight of all $u \leadsto v$ paths is equal, for every $u, v \in V$ (this is zero ...
119 views

### How to find the path for the most negatively-weighted cycle which goes through a specific source node?

I am trying to find the path for the most negative cycle in a graph G which starts and ends at a specified source node S. I have studied an application/ extension of the Bellman-Ford algorithm (...
128 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 ...
417 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 ...
71 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 ...
328 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: ...
166 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 ...
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 ...
152 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 ...
22 views

### Finding the minimal path from S to T that visit all vertices

So I have a complete and directed graph with weights. I wish to find the shortest path from S to T that visits all other vertices in the graph at least once. Another important piece of information I ...
13 views

### Relation between shape descriptors and featured connected component in matching problems

Hope I'm asking in the correct community, from the title, I need a clarification regarding the idea of dealing with 3d descriptor and featured connected components. I have this approach: model -> ...
34 views

### Weight of minimum spanning tree of G and T

We have undirected weighted connective graph $G=(V,E)$, We also have a minimum spanning tree $T$ of $G$. Let $v$ be some vertex. We have new graphs, $G'$ and $T'$. $G'$ and $T'$ are same $G$ and $T$, ...
92 views

### Remove a vertex from a graph keeping shortest path distance same

How could we delete an arbitrary vertex from a directed weighted graph without changing the shortest-path distance between any other pair of vertices? We are allowed to reweight the edges.
24 views

### How to compute the predecessor-subgraph in all-pairs-shortest-paths algorithm?

The following slow algorithm (implemented from CLRS book) which runs in $\Theta(V^4)$ works fine for computing shortest paths distances: ...
95 views

### What is the difference between nearest and cheapest insertion algorithms for a Traveling salesman problem?

I know that in the cheapest insertion algorithm we include the node which is not in the "base group" that has smaller cost given all possible combinations, and for the nearest we include the node with ...
62 views

### Verifying the minimum cost from each node to a sink node in linear time

Problem Statement: Let $G= (V, E)$ be a directed graph with costs $c_e \in \mathbb{R}$ on each edge $e \in E$. There are no negative cycles in $G$. Suppose there is a sink node $t \in V$, and for ...
30 views

### Divide directed weighted graph into two parts

I have a directed, weighted graph $G = (E,V)$. For example, one might be $|E| = 74000, |G| = 725$. I want to divide this graph into two parts/clusters/communities, taking the edge weights into ...
24 views

### Learning the weights in a directed acyclic graph

I have a directed acyclic graph $G=(V,E)$ where each vertex $v$ is associated with a weight $w_v$ such that $$w_v=1+\sum\limits_{(v,v')\in E} w_{v'}$$ and $w_v=1$ in case $v$ is a leaf. I am trying ...
17 views

### Does the weighted max cut problem have applications to machine learning? If so, what are they?

At first, I thought the weighted max cut problem (WMCP) could be of use to binary classifiers, but since the standard WMCP doesn't have any "node groups must be on opposite side of a straight line" ...
55 views

### gas station problem variation

A question from an exam: Input:   A map of a country with distances (in km) on roads. some cities have gas stations.    The map is given in the form of directed ...
For a flow network $G=(V,E)$ where $s,t \in V$ and capacities $c_e>0$ for $e \in E$. A flow $f$ is given. How can I check whether of not $f$ is a valid flow within the network?
Suppose one has a tree with each node weighted with a tuple (say, some fixed $2$ dimensions, for now) of integers. Now we query the tree with two vertices $x$ and $y$ and a range $[a,b]\times [c,d]$, ...