Questions tagged [weighted-graphs]
Questions about graphs in which every edge is associated with a weight.
0
votes
0answers
23 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 ...
0
votes
1answer
38 views
The cheapest path in the graph
I am supposed to decide, if the statement is true or false and use arguments for my answer.
In every weighted n-vertices graphs:
with no negative weighted edges,
with n>10,
in which every weighted ...
0
votes
0answers
19 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
1answer
37 views
Single-source shortest paths with even weight
I need help to find an algorithm that calculates the single-source shortest paths in a graph, with an extra condition that the weight of the path has to be even.
In another words, we have to find the ...
0
votes
1answer
28 views
Uniqueness of minimum spanning tree
If G has a unique minimum spanning tree, does that mean the edge weights in G are also unique? if yes why and if no why?
0
votes
0answers
31 views
Define the time complexity of Kruskal's algorithm as function
I am trying to define the time complexity of Kruskal's algorithm as function dependant on:
the number of vertices V
the number of edges ...
0
votes
0answers
34 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
21 views
Whats the time complexity of Prims Algo. without heaps (using priority queue)?
Here's my attempt:
Initialisation -
...
1
vote
1answer
82 views
Djikstra's algorithm to compute shortest paths using at least k edges
I have a graph G = (V, E) where each edge is bidirectional with positive weight. I want to find the shortest path from vertex s ...
1
vote
1answer
58 views
Multiple Source Shortest Paths in a weighted graph
In an unweighted graph, we can find Multiple Source Shortest Paths using the Breadth-First Search algorithm by setting the distance of all starting vertices to zero and pushing them into the queue at ...
3
votes
1answer
52 views
Maximal Minimum Spanning Tree by Removing $k$ Edges
The problem is as follows:
Consider a connected, undirected, and weighted graph $G = (V, E, w)$ and an integer $0 < k < |E| - |V| + 1$. Describe and analyze and efficient algorithm to remove ...
2
votes
1answer
101 views
Given directed connected weighted graph, check if d(v) = delta(s,v)
I'm having some hard time with this problem.
Can someone give me some clue/guidance?
This is an homework question, so please don't just solve it.
Given a weighted directed connected graph $G = (V,...
3
votes
1answer
103 views
Constructing a minimum spanning tree from an all-shortest path graph?
Given an $n \times n$ shortest path distance matrix $D$. And a complete graph $G(D)$ on $n$ nodes, where edge $(i, j)$ has weight $D_{ij}$. Furthermore, the distance matrix $D$ is computed for a ...
2
votes
2answers
82 views
Given all pairs shortest paths matrix, find graph with minimum total sum of edges
I was looking at some problems about graphs, and I got stuck on this one. Namely, we have given matrix of size $N \cdot N$ representing the length of the shortest path in undirected graph between some ...
2
votes
2answers
118 views
Floyd Warshall's All pair shortest path problem does not evaluate all possible paths
We know that the FW all pair shortest path is a Dynamic Programming (DP) approach to solving the problem. Being a DP, it smartly evaluates all possible options before deciding the final option at each ...
3
votes
1answer
77 views
Is maximum edge-weighted triangle-free graph NP-hard?
Given a graph $G$ with weights $w_e$ on the edges, choose a subset $S$ of the ''edges'' such that $S$ doesn't contain any 3-cycles, maximizing $\sum_{e\in S} w_e$.
Is this problem NP-hard? I thought ...
1
vote
1answer
26 views
How is Johnson's shortest path weighting function $\hat{w}(u, v) = w(u, v) + h(u) - h(v)$ proven by the triangular inequility?
Recap to the Johnson's shortest path algorithm:
By the procedure extending the original graph $G^\prime = (V^\prime, E^\prime), V^\prime = V\ \cup \{s\}, E^\prime = E\ \cup \{(s, v)\ |\ \forall v \in ...
1
vote
1answer
58 views
Generating a random minimum spanning tree
I am tring to find the simplest method of generating a random minimum spanning tree.
My intention is to randomly generate a Level in a game where there are n amount of fixed sized rooms existing on a ...
-2
votes
1answer
390 views
Please indicate whether each of the following statements is TRUE or FALSE and provide a brief justification
I provided my answers in the "answer your own question" bit.
I have applied the same logic for my answers to a&b and c&c which seem to be essentially the same questions. Am I right though?
a)...
0
votes
1answer
41 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
64 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
38 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
125 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
31 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
36 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
99 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
55 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
26 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
171 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
90 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
71 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
296 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
92 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
70 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
68 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
611 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
34 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
209 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
68 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
89 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
39 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
116 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
343 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
...
3
votes
1answer
325 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
661 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
46 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
332 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
52 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
936 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 ...
