The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [weighted-graphs]

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

60 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
11
votes
0answers
503 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 ...
10
votes
0answers
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 ...
5
votes
0answers
537 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 ...
4
votes
0answers
343 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 ...
4
votes
0answers
351 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 ...
3
votes
0answers
76 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 ...
3
votes
0answers
118 views

How to find an optimal sequence of matching

Given a graph $G(V.E,w)$ Here $w: E \mapsto R$. We need to find optimal set of matchings(set of edges that have no common vertices) and $t_i$'s such that after all these matchings, it results in $\...
3
votes
0answers
82 views

Algorithm for finding the set of minimum coordinate pairs

Consider these two sets of coordinate pairs with weights: ...
3
votes
0answers
405 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_{...
3
votes
0answers
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. ...
2
votes
0answers
53 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 ...
2
votes
3answers
70 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 ...
2
votes
0answers
95 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 ...
2
votes
0answers
152 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 ...
2
votes
0answers
431 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 ...
2
votes
0answers
341 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 ...
2
votes
0answers
40 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
0answers
285 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 ...
2
votes
0answers
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 ...
1
vote
0answers
30 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: ...
1
vote
0answers
12 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 ...
1
vote
0answers
67 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 ...
1
vote
0answers
230 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 ...
1
vote
0answers
49 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 ...
1
vote
0answers
151 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). ...
1
vote
0answers
75 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 ...
1
vote
0answers
105 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 (...
1
vote
0answers
123 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 ...
1
vote
0answers
383 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 ...
1
vote
0answers
70 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 ...
1
vote
0answers
277 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: ...
1
vote
0answers
162 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
0answers
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 ...
1
vote
0answers
149 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
0answers
15 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: ...
0
votes
0answers
18 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 ...
0
votes
0answers
46 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 ...
0
votes
0answers
26 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 ...
0
votes
0answers
18 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 ...
0
votes
0answers
15 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" ...
0
votes
0answers
36 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 ...
0
votes
0answers
18 views

Check valid flow in a graph

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?
0
votes
0answers
36 views

Real-world scenario for a theoretical problem on trees

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]$, ...
0
votes
0answers
49 views
0
votes
0answers
103 views

Shortest path between 2 nodes subject to constraints

I am trying to find shortest path between 2 nodes in a graph similar to below: Each edge has a weight assigned to it. Also, the graph is directional with each edge directing from left to right. I ...
0
votes
0answers
35 views

create distance (ment is high difference between values) between Vertexes in a list

Given are some vertexes, arranged in a list (so there every vertex is connected with two others and there are no circles in the graph). Every Vertex contains one number. Now you can lower the Number ...
0
votes
0answers
75 views

minimum subgraph whose cost is greater than a predefined threshold

is there an approximate algorithm that takes as input: an weighted undirected graph $G = (V,E,W)$ and an integer $k > 0$ and outputting: a subgraph $g'$ with $w(g') \geq k $, and $|g'|$ is minimum....
0
votes
0answers
417 views

Creating admissible and consistent Heuristic function Help

I am trying to create a heuristic function for use in an A* algorithm. The problem to be solved is a single row tile puzzle with 3 total w tiles and 3 b tiles and one "_" tile as shown below WWW_BBB ...
0
votes
0answers
57 views

SimRank++ on a weighted graph (why the formula reflects the influncee of the weight)

In the paper "Simrank++:Query Rewriting through Link Analysis of the Click Graph"(http://www.vldb.org/pvldb/1/1453903.pdf), the formula to compute the similarity between $q$ and $q'$ is as follows: \...
0
votes
0answers
60 views

Listing all maximal cliques with mean edge weight at least k in a weighted complete graph

Given a weighted undirected complete graph G = (V,E). I am interested in finding all maximal cliques that have mean edge weight (mean of weights of all edges in the clique) at least k. Most of the ...