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.

Filter by
Sorted by
Tagged with
0
votes
1answer
53 views

More efficient maximum bipartite matching

I've been looking into weighted matching in bipartite graphs and am currently looking at maximum matchings in weighted bipartite graphs. As I've been reading and poking around at different books and ...
3
votes
1answer
85 views

Algorithm for minimizing the number of “inversions” in a graph

Given the following graph: With the assumptions below: A node on the left is linked to several nodes on the right Nodes on the right are paired together: one is black, one is white Each pair of ...
2
votes
2answers
39 views

Traversing a graph in finite time, maximizing utility

I am working on a problem in robotics, where we have a problem of having finite time horizon T, and a set of actions. Each take some time to perform and each have a utility. We can transition from any ...
1
vote
0answers
226 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
1answer
34 views

Manber's graph-partitioning implementation

I'm having trouble understanding a part of Manber's graph-partitioning algorithm, presented in A Text Compression Scheme that Allows Fast Searching Directly in the Compressed File. Generally speaking ...
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
1answer
94 views

Finding a minimum weight path with certain restrictions

I have a directed weighted multigraph whose vertices are sets of URLs. We add to this multigraph all edges of the form $i\to j$ where $i\subset j$ (such edges are of zero weight), where $i$, $j$ are ...
1
vote
2answers
27 views

Representing a network with two types of connections: A fishing application

I want to represent a fishing network using a graph representation. My question surrounds how I can write the adjacency matrix if there are two types of connections, which I want to capture together. ...
6
votes
2answers
194 views

Path in an edge-weighted undirected graph

Is it an $NP$-hard problem? You're given an undirected graph $G(V,E)$ with edge weight $w: E \to \mathbb{N}$ and a function $\mathrm{max}$-$\mathrm{visit}: V \to \mathbb{N}$ and a number $W$ in unary....
2
votes
1answer
93 views

Path in a vertex-weighted undirected graph

Is it an $NP$-hard problem? You're given an undirected graph $G(V,E)$ with vertex weight $w: V \to \mathbb{N}$ and a function $\mathrm{max}$-$\mathrm{visit}: V \to \mathbb{N}$ and a number $W$. Does ...
2
votes
1answer
109 views

Mimimum spanning tree with a constraint on number of certain types of edges

I have the the following problem. Say we have a graph $G = (V,E)$ where all $e \in E$ have positive weight, and $E$ can be separated in to two disjoint sets $E = A \cup B$. We have to find a spanning ...
2
votes
1answer
22 views

Marginalise edge weights on graph

I have a directed acyclic graph with a score on each edge. The score of a path is defined to be the sum of the scores on the edges along this path. The probability of a path is the score of such a ...
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 ...
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
1answer
95 views

Maximize vertex cover weights with bounded edge weights in a connected subgraph

Similar questions were asked elsewhere, but no satisfying answers occurred yet. In a graph with weights for both vertices and edges, I want to find a subgraph, whose sum of internal edge weights is ...
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 ...
0
votes
3answers
682 views

Find longest path in graph with N nodes and N edges

We have given weighted undirected connected graph with $n$ nodes and $n$ edges, we want to find the longest path in it. Note that the path should be in each node at most once. Since the graph has $n$ ...
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 ...
1
vote
1answer
257 views

Find the center node on a weighted, non-directed graph

So I have a problem, and it's an assignment from school. This is a figure made out of matchsticks. The goal is to find the optimal location to light up the figure so that it burns in minimal time. ...
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....
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
1answer
69 views

Maximum flow in a graph, and conservation of flow

The requirement for the conservation of flow in a flow network is, as I see it in the MIT lectures on Algorithms, that $\sum_{v\in V}f(u,v)=0$ for every $u\not\in \{s,t\}$ where $s,t$ are the source ...
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 ...
0
votes
0answers
416 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 ...
2
votes
1answer
405 views

Avoiding loops in Bellman-Ford algorithm

If you apply standard Bellman-Ford algorithm to a graph containing negative loop it can only report its existence. Are there approaches to modify it to find shortest path containing any vertex not ...
0
votes
3answers
866 views

Decreasing the weight of one edge of minimum spanning tree, prove the MST is unchanged

Suppose an edge $e$ is in a minimum spanning tree $T$ of a graph $G$. If the weight of $e$ decreases by some positive number, how to prove the the MST is unchanged (still $T$) ? It seems obvious by ...
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: \...
2
votes
1answer
394 views

Applying Johnson's algorithm on undirected graph with negative edge weights

Currently we are discussing applying Johnson's algorithm on undirected graph with negative edge weights. And the graph may contains cycles, but the sum of weights of any cycle is guaranteed to be non-...
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 ...
5
votes
1answer
1k views

Konig's Theorem for Min Weight Vertex Cover?

Koning's theorem states that the cardinality of the maximum matching in a bipartite graph is equal to the size of its minimum vertex cover. Wikipedia states that there is an equivalent version of the ...
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 $\...
0
votes
1answer
78 views

Dijkstra algorithm step in Introduction to Algorithms

In the introduction to algorithms proof of Dijkstra, I don't understand why the statement "both y and u were in V-S when u was chosen". We add x before y, and so we relax d[y] with the the edge $$\...
0
votes
1answer
61 views

Algorithms : most lightweight circle in directed graph that goes through specific vertex

I have directed Graph G(V,E) with weight function w. so that weight of each (u,v) is a positive value. I need to find the most lightweight circle in the graph that vertex k' is part of it. I've also ...
1
vote
1answer
155 views

How to restore a broken minimal spanning tree?

We're given $T$ a minimal spanning tree (MST) of a non-directed, connected graph $G=(V,E)$ with non-negative weights for each edge $e \in E$. Let $e^* \in T$ be an edge in $T$ and let $G'=(V,E')$ be ...
2
votes
2answers
75 views

Reconstruct graph of N edges from a matrix of shortest pair distances (N*N) (i.e. result from Floyd-Warshall algorithm)

I want to reconstruct a graph when given the results of a Floyd-Warshall shortest pair distances matrix, similar to the problem being solved in this question: Is it possible to reconstruct graph if ...
0
votes
0answers
245 views

Clustering based on weights of edges

I have a weighted graph representing traffic network. Nodes represent the locations and vertices represent available paths between locations. Weight values represent number of the passages on the path....
1
vote
0answers
39 views

Is a spanning tree an MST if its weight can't be decreased by adding an edge and removing one? [duplicate]

My gut says it's true and I have tested it on a few examples. However, I can't prove it. I thought of using contradiction; suppose there exists another tree T' with smaller weight which has m edges ...
1
vote
1answer
600 views

Routing algorithm for train network

I am trying to analyse a weighted multi-graph which represents a snapshot of a rail network for a particular day. As such, the vertices of the graph can be considered stations and the weighted edges ...
0
votes
1answer
275 views

Longest path in a DAG: source to sink?

Is the longest path in a (weighted) DAG always from a source to a sink? This seems correct to me by intuition, but I'm not 100% confident. Like, for example, if I had an array in which each index ...
-1
votes
1answer
413 views

Finding multiple shortest path trees from an undirected, weight graph

In an undirected, weighted graph G the set of shortest paths from an arbitrary start vertex s form a spanning tree of G. We're calling this spanning tree a shortest path tree. How do I find an ...
1
vote
1answer
63 views

Understanding characterizations of Matching on Graphs

I am studying Matching Theory on Graphs and I am wondering if I understand the characterization of the problems right. Definition: Let $G = (V, E)$ a graph. A set $M \subseteq E$ is called a matching ...
2
votes
1answer
629 views

Single pair shortest path algorithm with time a constraint

I am trying to solve the shortest path problem between n cities. Any single pair shortest path algorithm such as Dijkstra's and Bellman-Ford would work here, but if we add a simple additional ...
1
vote
1answer
167 views

Find minimum time path between two nodes

I am trying to write an algorithm for finding best path for an electric vehicle to navigate through network of chargers. A graph with Vertices representing charges and Edges representing distances ...
1
vote
1answer
116 views

Algorithm to calculate average weight from every pair of nodes [duplicate]

I'm trying to solve a puzzle where I need to calculate the average weight between every node in the graph. For example, for the following graph: The results is calculated like this: 1 -> 2 = 3; 1 -...
1
vote
1answer
442 views

Shortest paths when edge weight depends on previous edge

I have a directed graph with non-negative weights on the edges. I can divide the nodes in two "classes", X (roughly 1700 nodes) and Y (~300). I want to collect all the shortest paths from x in X to y ...
3
votes
2answers
593 views

Girth of Undirected Graph with Positive Integer Weights

Let $G = (V, E)$ be an undirected graph without self loops and with edge weights $w: E \to \mathbb{N}$. The girth $g(G)$ of $G$ is defined as the length of the shortest cycle in $G$, i.e. $g(G) := \...
5
votes
3answers
431 views

Is it possible to reconstruct graph if we have given matrix of shortest pairs

I'm trying to reconstruct graph if we have given the result of floyd-warshall algorithm, more formally: Let's say we have given undirected weighted tree (graph without cycles) with $N$ nodes, such ...
0
votes
0answers
40 views

Is it possible to find all shortest paths in undirected weighted graph in polynomial time [duplicate]

I'm trying to practice some theory on graphs: Namely, we have given connected undirected weighted graph with $N$ nodes and $M$ edges, let's say we want to find the shortest paths between node $1$ ...
0
votes
0answers
41 views

Spectral clustering algorithm doesn't use all available clusters

We have implemented a spectral clustering algorithm according to the article Multiclass Spectral Clustering (Yu and Shi, Proc. IEEE ICCV '03, vol. 2, pp. 313–319, 2003; PDF). We used ...