Questions tagged [weighted-graphs]
Questions about graphs in which every edge is associated with a weight.
199
questions
1
vote
1answer
28 views
I came up with a way to modify Dijkstra's Algorithm to handle graphs with negative edge weighs [duplicate]
Add a constant $c\geq |w_{min}|$ to each edge of $G$, so that each edge now has non-negative weight.
Run Dijkstra's algorithm
Can anyone tell me if this is viable or if it fails?
3
votes
1answer
79 views
Minimum Path cover in a Directed Acyclic Graph
Given a weighted directed acyclic graph $G=(V,D,W)$ and a set of arcs $D'$ of $D$, where the weights of $W$ are on the vertices. The problem is to partition $G$ into a minimum number of vertex-...
0
votes
0answers
11 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
42 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
1answer
46 views
Longest path in a directed acyclic graph with constraints
Given a directed weighted acyclic graph G=(V,D,W) and a subset of edges D' of D. The problem is to find the longest path in G that passes by exactly one edge of D'.
What is the complexity of this ...
0
votes
1answer
20 views
Conceptual explanation of negative weights? [duplicate]
What conceptually are negative weights on graphs? Why might they have them?
0
votes
0answers
25 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
1answer
24 views
Weighted graph clustering with maximum size constraint
I'm currently trying to solve a clustering problem. I need to cluster/partition an undirected weighted graph into groups that are restricted to size n.
I have ...
2
votes
2answers
80 views
For what applications of the traveling salesman problem, does visiting each city at most once truely matter?
Traditionally, the traveling salesman problem has you visit a city at least once and at most once.
However, if you were an actual traveling salesman, you would want the least cost route to visit each ...
0
votes
0answers
16 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 ...
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 ...
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:
...
0
votes
0answers
13 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" ...
3
votes
2answers
257 views
Weight functions in graph algorithms
In text books, for instance in the 3rd edition of Introduction to Algorithms, Cormen, on page 625, the weights of the edge set $E$ is defined with a weight function $w:E\rightarrow \mathbb{R}$.
Why ...
0
votes
0answers
28 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 ...
1
vote
1answer
37 views
Path of exact cost k in DAG
struggling with this question from an exam:
input:
DAG G=(V,E). each edge $e_i$ has weight $w_i\in \text{{0,1,2,3}} $
Two vertices : s,t
Number: k
output:
...
3
votes
0answers
38 views
Alternative criterion for approximate maximum-weight perfect matching algorithms [closed]
Is there any literature on approximate maximum-weight perfect matchings where the approximation criterion is not the factor between the approximate and exact weight sum achieved by each solution, but ...
0
votes
0answers
16 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?
3
votes
1answer
61 views
Algorithm to compute sum of cost of all path between pair of unique vertices of a tree
Given tree is undirected graph. It has n vertices and n-1 edges. The algorithm should compute the sum of cost of all path between pair of unique vertices.
Thus, there are total nC2 or n(n-1)/2 such ...
1
vote
2answers
73 views
What is the graphic TSP?
I'm not sure if I understand the following definition of the (well-known apparently) Graphic TSP, also known as graph-TSP :
...graph-TSP, that is, the traveling salesman problem where distances ...
3
votes
0answers
73 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 ...
0
votes
1answer
38 views
Finding the maximum disjoint weight in a weighted node graph
I have a graph of nodes that reflect resource allocation. Each node has a weight to reflect this. A well formed graph is disjoint, so there will be no edges, and the weight of the graph is just the ...
0
votes
0answers
21 views
Single source shortest paths with even path [duplicate]
Given directed graph with non negative weights and vertex s.
I need an algorithm that finds shortest paths from s to all vertices and the paths have to be even.
1
vote
1answer
58 views
Maximum weight vertex-disjoint paths
I have a complete (every vertex is connected by an edge to every other vertex) undirected positively weighted graph. I want to find vertex-disjoint paths in the graph whose total weight is as large ...
2
votes
3answers
64 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 ...
1
vote
0answers
11 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 ...
0
votes
1answer
43 views
The cheapest path in the graph [duplicate]
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 ...
1
vote
0answers
65 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
119 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
38 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
77 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
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
48 views
Whats the time complexity of Prims Algo. without heaps (using priority queue)?
Here's my attempt:
Initialisation -
...
1
vote
1answer
181 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 ...
2
votes
1answer
267 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
103 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
152 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
119 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
187 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
201 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
86 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
30 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
73 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
525 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
48 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
78 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
200 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 ...
