Questions tagged [weighted-graphs]
Questions about graphs in which every edge is associated with a weight.
3
votes
1answer
54 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
22 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
34 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
103 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
36 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
60 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
36 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
60 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
30 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
26 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
68 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
46 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
24 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
147 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
84 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
53 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
21 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
166 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
72 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
48 views
Single source shortest Path Algorithm in dynamic graph
In case of dynamic graphs where edges are added only (all edges have positive weight).
Goal: to keep track of the shortest path from the source to the goal node.
Are their any specific conditions ...
0
votes
1answer
51 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
60 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
522 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
32 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
42 views
Why do we use Bellman ford instead of Dijkstra's Algorithm? [duplicate]
I read that Bellman ford is preferred over Dijkstra's algorithm when there are negative edge cycles in the graph. So, by using Bellman ford we can detect cycles in O(EV) where E are no. of edges and V ...
1
vote
1answer
178 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
59 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
51 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
28 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
86 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
299 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
253 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
459 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
44 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
254 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
44 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 ...
4
votes
1answer
732 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
102 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
71 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
47 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
110 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
51 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
103 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
0answers
399 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
224 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
293 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
57 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
447 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
99 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 ...
