Questions tagged [weighted-graphs]

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

Filter by
Sorted by
Tagged with
1
vote
0answers
15 views

How to find if there's an MST where vertex $v$ has degree 2 in it? [duplicate]

I've faced this question and I hope that someone can help with it. Question: We're given an undirected graph $G=(V,E,w)$ where $w\colon E\rightarrow \mathbb{Q}$ and vertex $v$. We want to find if ...
1
vote
1answer
49 views

How to find lightest path in directed weighted graph where each edge has a color

We're Given a directed graph $G = (V, E)$ and a weight function $\omega : E \rightarrow \mathbb{Z}$. Each edge is colored with one of these colors: Red, Green, Blue. Given two vertices $s,t \in V$, ...
7
votes
11answers
4k views

Real life examples of *zero* weight edges in graphs

The meaning of edges with zero weight in a weighted graph questions me for a long time, and I even asked a related question previously. Yet, when I recently read here a question on real life example ...
7
votes
0answers
212 views

Shortest path in directed graphs with no more than $\log \log n $ negative edges

Given a directed graph $G=(V,E)$ with $|V|=n$ vertices and some weight function $w\colon E\to \mathbb{R}$, I also know that there are at most $\log\log n$ negative weight edges in $G$, and $G$ does ...
18
votes
6answers
3k views

Real life examples of negative weight edges in graphs

I am unable to relate to any real life examples of negative weight edges in graphs. Distances between cities cannot be negative. Time taken to travel from one point to another cannot be negative. ...
1
vote
1answer
66 views

Shortest walk from $u$ to $v$ through $w$

We have an undirected, weighted graph $G=(V, E)$ with two weight functions $W_1 : E \rightarrow \mathbb{R}^{+}$ and $W_2 : E \rightarrow \mathbb{R}^{+}$ such that for every $e \in E$ we have $W_1(e) &...
1
vote
1answer
81 views

There are n cities and m possible bidirectional roads and k temple. build roads with minimum cost such that each city has access to at least 1 temple

There are n cities and m possible roads and k temples. The cost of each road is given. Build ...
6
votes
3answers
1k views

Does the Minimum Spanning Tree include the TWO lowest cost edges?

Wikipedia's Minimum Spanning Tree reads: Minimum-cost edge If the minimum cost edge e of a graph is unique, then this edge is included in any MST. Proof: if e was not included in the MST, removing ...
2
votes
1answer
49 views

Is the MCP language really np hard?

I have a graph $G=\left(V , E\right)$ and source $s$ and target $t$. I also have a weight function $w: V\rightarrow \mathbb{R^+}^k$, meaning a vertex given $k$ non negative weights. There is an upper ...
3
votes
1answer
25 views

On a coloring that uses $2\cdot a\left( G \right)$ colors

Denote $G=\left( V, E \right)$ arboricity by $a\left( G \right)$. I'm trying to understand why $G$ is $2\cdot a \left( G \right)$-colorable. I came across this post. Both the OP and the answer say ...
3
votes
0answers
63 views

Coloring nodes and edges in node-weighted graph

I have a graph $G$ with $n$ nodes and $O(n)$ edges. Each of the nodes has a positive integral weight at least 2, such that sum of all weights is at most $O(n)$. We want to color the nodes and edges ...
1
vote
1answer
30 views

Linear deterministic algorithm for finding spanning tree T with minimal maximum edge

Given an undirected connected graph $G = (V, E)$ with weights $w : $E → $R$$^+$, define for a spanning tree T the value $λ$(T) = $max_e$∈$T${w(e)} (the maximal edge weight in T ). I need to find a ...
0
votes
1answer
25 views

Minimum spanning tree where weights of edges are intersecting sets

Given Graph $G=(V, E)$, where each edge in $E$ is assigned a "weight" as a set of elements. $w(e) = S_e \ \forall e \in E$. Find a subset $E' \subset E$ such that it spans $G$, i.e., $E'$ ...
0
votes
1answer
26 views

Does the A* algorithm visit every node in an undirected graph when no path to the goal node exists?

When no path to the goalnode exists, does the A*-Algorithm a) visit and b) expand every node in an undirected graph? I have a monotone heuristic. Thanks
1
vote
0answers
41 views

What if have a algorithm that could generate a NFA of 42 states of any binary string of 2^32 length?

For example, if we have a true algorithm that could generate any NFA of at most 42 states from any binary string of 2^32 length. So, this algorithm can not just recognize the string but just recreate ...
2
votes
2answers
80 views

Given DAG $G(V,E)$, find $\forall v \in V$ the sum of the weights of vertices that are reachable from the $v$

Given a DAG $G=(V,E)$ and a weights function on the vertices $w:V \to \mathbb{R}$, suggest an algorithm that computes for every $v \in V$ the sum of the weights of vertices that are reachable from it. ...
2
votes
0answers
31 views

Minimum unrooted binary spanning tree

Given a graph $G$ with $n$ tip vertices, $n-2$ internal vertices and a cost on each edge $C(v)$, find a minimum spanning tree subject to degree constraints: tips have degree $1$ internal vertices ...
-2
votes
2answers
44 views

Shortest path covering certain nodes in a graph

Consider a weighted graph where each node represents a city. Now a truck starts from a city A and it has to cover a set of cities ...
4
votes
0answers
52 views

Collision detection with vary constraints

I have an edge-weighted tree, and for each leaf of the tree, there's a corresponding point on the 2D plane. For each pair of points $u$ and $v$, let $d_{uv}$ be the distance of the corresponding ...
1
vote
0answers
64 views

Find two paths in a Graph which are disjunct in

Assuming we have two trains that start in one source edge. I want to find an algorithm that finds two paths for these trains so that they won't meet in an edge at any given time. So we have the train ...
0
votes
1answer
85 views

Prove Edited Algorithm of Bellman–Ford?

Please Note: I forgot a small detail which caused the algorithm to be incorrect, please read the new version and thanks for pointing that. I am stuck on this question for a week and hope to get some ...
1
vote
1answer
35 views

Polynomially Equivalent Pairs of Minimization-Maximization Problems in Weighted Graphs

I am studying computational complexity using Papadimitrious's book: "Computational Complexity". I am trying to solve Problem 9.5.14, about polynomially equivalent minimization-maximization ...
1
vote
1answer
172 views

Sorting criteria for Kruskal's algorithm

I am studying Kruskal's algorithm. Is the only acceptable sorting criteria to sort edges from lowest weighted edge to greatest weighted edge? I ask this because I assume that if the algorithm used an ...
2
votes
2answers
158 views

Bellman-Ford algorithm intuition

We recently learned Bellman-Ford algorithm for shortest path in class, but I didn't understand it. Can you give me intuition for why the algorithm works? And can you please explain why it is correct? ...
1
vote
1answer
24 views

Prune and search Algorithm for Generating a Bottleneck Spanning Tree

I'm trying to wrap my head around a prune-and-search algorithm for returning a bottleneck spanning tree, currently I'm selecting the median weight of all the edges, then divide the original graph G ...
4
votes
0answers
54 views

Find an optimal matching in a complete graph

I have a complete edge-weighted graph with $n$ vertices (and therefore $n\cdot(n-1)/2$ edges). I want to find a complete matching (i.e., perfect matching) in which the quotient $sum_G/A_G$ is maximal, ...
1
vote
2answers
82 views

Is the inverse of MST cut property true? Why?

If we partition the nodes of a graph into sets A and B, there is an edge e of weight larger than any other edge crossing the cut between A and B, e would never be in the minimum spanning tree?
1
vote
1answer
62 views

Variant of assignment problem

This is something like assignment problem, we have 2 group of people, first contains $n$ person and second contains $m$ person. we have a matrix $C$ which is an $n \times m$ matrix and our goal is to ...
5
votes
1answer
50 views

Maximum-weight set of cliques of size 3 with no common vertices in undirected graph

I'm looking for an algorithm/insight into a problem that's an extension of the Maximum Weight Matching problem. The maximum weight matching problem looks for the max-weight set of edges that contain 0 ...
2
votes
1answer
113 views

A more rigorous proof on a Bellman-Ford's corollary

The following corollary can be found at page 653 of "Introduction to algorithms (3rd edition)" Corollary 24.3 Let $G = (V, E)$ be a weighted, directed graph with source vertex $s$ and a ...
1
vote
2answers
292 views

Problem to understand a Bellman Ford algorithm exercise

I am trying to understand the following exercise from Introduction to algorithm (3rd edtion). Exercise 24.1-3 (page 654) Given a weighted, directed graph $G=(V, E)$ with no negative-weight cycles, ...
2
votes
1answer
43 views

Job Shop Problem: How do you get an ordered sequence of operations from the disjunctive acyclic graph?

Intro The job shop problem is a classic scheduling theory problem. Given $N$ jobs and $M$ machines, a typical goal of the JSP is to minimise the makespan (starting time of the last operation + its ...
1
vote
0answers
28 views

Running time of Goldberg's densest subgraph algorithm for integer edge weighted graphs

The running time of the original non-weighted algorithm is $\mathcal{O}(M(n, n + m)\,log(n))$, where $M(n, m)$ is the execution time for finding a min-cut in a network with $n$ nodes and $m$ edges ...
1
vote
2answers
65 views

Maximise the value of the minimum weight intra edge

I've been doing review problems for a midterm and I came across this one problem that I haven't been able to solve. The problem essentially says that given a complete graph $G=(V,E)$ partition the ...
1
vote
1answer
138 views

Find MST on grid graph with only weight of 1 and 2 in $O(|V|+|E|)$

Given a grid graph $G=(V,E)$ which has only two different integer costs/weights of 1 and 2. Find Minimum Spanning Tree in $O(|V|+|E|)$. I tried the following: Changing Kruskal using a counting Sort ...
2
votes
2answers
105 views

Find cycles with specific weights in complete graph

(this is a cross-post from mathoverflow) Assume I have an undirected edge-weighted complete graph $G$ of $N$ nodes (every node is connected to every other node, and each edge has an associated weight)....
1
vote
0answers
33 views

Find approximate 'best' matching pairs by calculating the fewest possible weights

My specific problem is as follows: Given two list of texts (in the order of 5 to 50 items) Find best matching pairs with their corresponding matching score (weight) Where each item can only be ...
1
vote
0answers
215 views

Finding s-t min-cut of undirected graph

Given an undirected graph with non-negative edge weights, and two vertices $s,t$ in the graph. I would like to find the minimal cut such that $s$ and $t$ are on different sides of the cut. For example ...
0
votes
1answer
23 views

Distance transform with variable "impedance"

The distance transform gives the distance of each pixel in a mask to the nearest zero. E.g. lets take the Taxicab distance transform: ...
0
votes
0answers
27 views

Cycles of a multigraph with a property on the edges

Let $n$ be a positive integer. On a circle are arranged $n$ points $A_1$, $\ldots$, $A_n$. We put some arrows from $A_1$ to $A_2$, from $A_2$ to $A_3$, etc., from $A_n$ to $A_1$. On each arrow are ...
1
vote
1answer
488 views

Is the minimum bottleneck spanning tree also a minimum spanning tree for an undirected graph with unique edge weights?

I can see a counterexample such as this: But I can also see in some cases it could be the same. I am trying to understand what property makes a MBST also a MST?
2
votes
1answer
158 views

Detecting cycles with weight zero in a directed graph

I am given a directed graph $G=(V, E)$ with a weight function $w: E\to\mathbb{R}$, that doesn't contain negative cycles. I need to find an algorithm that returns ...
2
votes
0answers
35 views

find zero weight cycles in a directed graph [duplicate]

I need to plan an algorithm that decides if a directed weighted graph $G = (V,E)$ has a zero weight cycle. the graph has no negtive cycles the algorithm needs to be in $O(|V| \cdot |E|)$ time my ...
0
votes
0answers
106 views

What is the significance of Bellman-Ford and linear programming for scheduling and makespans?

CLRS exercise 24.4-9 says the following: Show that the Bellman-Ford algorithm, when run on the constraint graph for a system $Ax \leq b$ of difference constraints, minimizes the quantity $\max_i\{x_i\...
0
votes
1answer
107 views

Vertices reachable from negative-weight cycles in Bellman-Ford

TLDR: I want to know if there's a simple way to fill in distances for all vertices reachable from negative weight cycles (not just ones on the cycle itself) once Bellman-Ford has found a negative-...
1
vote
1answer
98 views

Unsure why (or whether?) a certain algorithm correctly computes a Minimum spanning tree

CLRS problem 23-4 part c gives an algorithm that may or may not compute a minimum spanning tree. Given some connected undirected graph G, we have ...
2
votes
1answer
103 views

shortest path in color-weighted graphs

I want to find an algorithm to find the shortest path in a vertex-colored vertex-weighted graph. Every vertex with the same color has the same weight and the total weight of a path should be the sum ...
2
votes
1answer
120 views

How to define a path between two sets of vertices?

In section 17.2 of the book "Combinatorial optimization polyhedra and efficiency" by Schrijver, he describes the Hungarian method for maximum weight matching in bi-partite graphs (with ...
1
vote
1answer
29 views

Find sets of weighted objects to maximize number of sets with weight >= X

I have N objects, each of which has a weight. I need to form combinations of the objects to maximize how many sets of objects add up to at least x total weight. Combinations can consist of any number ...
1
vote
1answer
79 views

Finding an algorithm that minimizes vertex weight sum of a subgraph that satisfies several constraints

I have a vertex-weighted undirected graph $(V,E)$ with root vertices $R = {r1, ..., rn}$. I need to find the subset $V'⊂V$ such that $R⊂V'$, $N[V']=V$, $∀v'∈V '[∃r∈R ($path($r', v'$)$)]$ that ...

1
2 3 4 5
7