Questions tagged [weighted-graphs]

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

Filter by
Sorted by
Tagged with
2
votes
1answer
247 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 ...
3
votes
2answers
168 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 ...
2
votes
2answers
62 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?
1
vote
1answer
348 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
38 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
60 views
2
votes
1answer
397 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 ...
3
votes
1answer
872 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
228 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
212 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
160 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
508 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
280 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
112 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
35 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
115 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
718 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
75 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
94 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
40 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
299 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
53 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
185 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
183 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
29 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
200 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
95 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
157 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
363 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
137 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
111 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
82 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
749 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
39 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
324 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
84 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
120 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
94 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
187 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
473 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
484 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
1k 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
63 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
478 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
61 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
123 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
81 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 $$\...