Questions tagged [weighted-graphs]
Questions about graphs in which every edge is associated with a weight.
395 questions
1
vote
0
answers
28
views
Hypergraph partitioning constrained on partition size
I have a $k-$uniform hypergraph $H=(V,E)$ with $n$ vertices. I need to partition $H$ into two partitions of sizes $r$ and $n-r$. Is there an approximating algorithm that can do this while minimizing ...
- 111
2
votes
1
answer
62
views
Maximum cardinality matching with a priority order
Problem Setup
Let's say we have a bipartite graph $(U, V)$ where the nodes of the graph are labelled with a positive integer and each edge $(u_i, v_i)$ has $u_i < v_i$. Our goal is to find a ...
- 105
0
votes
1
answer
116
views
Dijkstra's Algorithm for Directed Graphs with Negative Edges Without Cycles
I came across a modified version of Dijkstra's algorithm that is said to handle graphs with negative edge weights, provided there are no negative cycles. I'm particularly interested in understanding ...
- 121
0
votes
1
answer
133
views
traveling salesman problem to time dependent traveling salesman problem
Everyone knows about the traveling salesman problem, but in most real world applications the time dependent traveling salesman problem is a much better model. Since most people seem to focus on the ...
2
votes
1
answer
81
views
Finding a perfect matching that minimizes a cycle weight
We are given a complete bipartite graph with positive weights on the edges (as in the assignment problem). Initially, all edges are directed from left to right, as in this example:
We have to compute ...
- 6,131
1
vote
0
answers
57
views
Finding negative cycle in a multi/hyper graph?
I have the following problem:
Suppose I have n items and there is an exchange ratio for the items, $K_{ij}$ tells me how many items of type $j$ I will receive for $1$ unit of item $i$.
Question: Is ...
- 796
1
vote
1
answer
104
views
How Floyd–Warshall algorithm prevents the formation of cycles
I have trouble understanding how Floyd–Warshall algorithm prevents the formation of cycles during its iterative computation of shortest paths. Specifically, my confusion arises from this:
Independent ...
- 125
1
vote
2
answers
129
views
Why Can Johnson’s Algorithm Handle Negative Weights but A* Cannot?
I'm trying to understand why Johnson’s algorithm can handle graphs with negative edge weights by using a potential function, while A* cannot, even though both use similar weight adjustments.
Johnson’s ...
- 125
0
votes
0
answers
99
views
Maximizing Edge Sum
So there is this question :
we are given a tree with n nodes. For each node, $i$ we are assigned two values : a $r_i$, that is the right boundary, and a $l_i$, which is the left boundary. We should ...
- 45
3
votes
1
answer
107
views
Other vertices on the shortest path between two specific vertices
I have been trying to solve a question that says in a directed graph with n vertices and m edges whose weights are all positive integers, we have specified two of them, namely $a$ and $b$. We want to ...
- 45
2
votes
0
answers
51
views
Is spanner a subgraph?
I've recently came across Spanners and Emulators, which seem to be pretty much the same thing, apart from whether or not the approximation is multiplicative or additive. However, I saw that a $k$-...
- 557
1
vote
0
answers
28
views
Is the Chu-Liu/Edmond algorithm greedy in some cases?
I was learning about arborescences in graphs and came across the Chu-Liu/Edmond algorithm for finding the minimum-weight arborescence in a given directed graph.
The authors start with the premise that ...
3
votes
2
answers
240
views
Approximation Algorithm for Feedback Arc Set on a Sparse Graph
When looking at the feedback arc set problem, given some graph $G = (V, A)$ where the weights are on the arcs, I'm hoping to find an approximation algorithm that provides a guarantee when the number ...
- 33
1
vote
1
answer
226
views
Optimizing node removal in a graph to achieve minimal edge weights while maintaining a certain total node weight
In the graph above with weighted edges and nodes (node weights in parenthesis), I have a goal of reducing total edge weight. I can achieve this by simply taking out nodes and thereby removing edges, ...
1
vote
0
answers
41
views
Optimally sampling edge weights on a graph
I am working on some network problems where we do not know the underlying edge weights on the network precisely. All we know is that for a (directed) edge $(u,v)$ in the network, the weight $w(u,v) \...
- 23