Questions tagged [weighted-graphs]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
52 views

Find an independent set in which the cumulative sum of weights is maximized

I have a weighted undirected graph G=(V,E,W), I want to find an independent set S of V, such ...
Farah Mind's user avatar
1 vote
0 answers
15 views

Finding optimal threshold using small world network metrics to binarize 2 groups for comparison

I have two groups (GROUP1 and GROUP2) of undirected weighted graphs - one having properties more similar to small world network and other relatively random. These are represented as adjacency matrices ...
Vishwani Singh's user avatar
2 votes
1 answer
53 views

Does the Nth iteration of Bellman-Ford relax every edge reachable from a negative cycle?

Consider a graph $G$ with $N$ nodes, with the distance of each node initially set to infinity (there is no start node). If there are no negative cycles in the graph, then after $N - 1$ iterations of ...
dav's user avatar
  • 123
4 votes
0 answers
142 views

Negative cycle of even length

Given an undirected graph $(V,E)$ with weights on edges $\in Z$ is it possible to find a negative cycle of even length (not the weight of the cycle, but the number of edges contained in the cycle) in ...
Bait Hoven's user avatar
1 vote
1 answer
62 views

Running time of modified BFS algorithm to find shortest path in weighted DAG

While the shortest path can be calculated with $O(V+E)$ time over a weighted directed acyclic graph using topological sort, I wonder about the running time of the following BFS type algorithm I ...
wsz_fantasy's user avatar
0 votes
0 answers
27 views

Distance to specific node incremental addition

Let us say I have an empty graph G and a list of nodes N to add to the graph one-by-one. Let us say that I will have a node <...
OlorinIstari's user avatar
1 vote
1 answer
61 views

number of edges that appeared at least in one shortest path

In a simple weighted graph, with n vertices and m edges , for each pair of vertices we want to find the number of edges that appeared at least in one of the shortest paths between these two vertices. ...
mostamele's user avatar
0 votes
1 answer
79 views

Shortest Hamiltonian Path in a Complete Graph

I know that, in general, the Shortest Hamiltonian Path Problem in a general weighted graph is NP-complete. I am wondering, however, if the restriction to a complete weighted graph admits an algorithm ...
WakkaTrout's user avatar
1 vote
1 answer
28 views

Algorithm for constructing a numbering reflecting the order of activities

I'm following a book about graphs and they introduce a concept called 'activity network'. In an activity network, each vertex represents an activity in a project (like building a house for example) ...
BMBM's user avatar
  • 219
1 vote
1 answer
24 views

Graph Algorithms (SSSP vs MST)

I am currently facing a question "Can a graph with a unique MST product a different spanning graph using Dijkstra vs using Prim's algorithm?" The answer is false and I am struggling to ...
pehperclip's user avatar
0 votes
1 answer
48 views

Can Dijkstra's algorithm be used this way?

Let us say that I wanted to solve a Hamiltonian path problem by treating it as a Hamiltonian cycle(on a weighted graph). I use a TSP solver, and implement a dummy node of edge weight zero, whose ...
Johnny Upman's user avatar
0 votes
1 answer
58 views

How to modify Dijkstra's algorithm to model the path of an electric car?

I know that Dijkstra's algorithm is used to find the shortest path between nodes in a weighted graph. And I know that this can be used to model road networks. Somebody online asked (but nobody ...
Johnny Upman's user avatar
0 votes
0 answers
13 views

Constructing a sparse subgraph of original weighted undirected graph with approximation algorithm

In Kruskal's algorithm, we sort edges from least weight to greatest weight and add the edge if and only if both endpoints are in different connected components in current iteration. Now the question ...
vyjtkbyykyhuk's user avatar
0 votes
1 answer
55 views

Finding min s-t cut of network with flow on the nodes

Given a network with flow on the nodes. How can we find min s-t cut in a network with flow on the nodes? We know how to find min s-t cut whenever there’s a network with flow on the edges (Ford ...
Almog David's user avatar
0 votes
0 answers
39 views

Running time of variant of Dijkstra's algorithm

Consider the problem of finding the shortest-path distances from an origin vertex to all other vertices in a digraph. Normally in Dijkstra's algorithm, we visit the vertex whose shortest distance from ...
Andrew's user avatar
  • 287
1 vote
1 answer
55 views

Bipartite matching with constraints on one part

We have a bipartite graph with parts $A$ and $B$, and it is edge weighted. We have some constraints for part $B$. Each constraint is in this format: Between vertices $b_1$ and $b_2$ both from part $B$,...
Soroush Vahidi's user avatar
1 vote
0 answers
26 views

What is the name of this extension of the maximum independent set problem?

Problem: we have an undirected graph. Each vertex $v$ has a weight of $w_v$. For each vertex $v$, a nonnegative number $a_v$ is given, and for each edge $e$, a nonnegative number $b_e$ is given. ...
Soroush Vahidi's user avatar
1 vote
0 answers
59 views

What is the name of this matching problem?

We have a bipartite graph consisting of parts $A$ and $B$. Each vertex $i$ of part $A$ has weight $w_i$ and capacity $c_i$. We say a vertex $i$ in part $A$ is satisfied if at least $c_i$ adjacent ...
Soroush Vahidi's user avatar
3 votes
1 answer
134 views

Path planning on 2D grid graph to maximize the neighboring grid points of a path: Can we do better than brute DFS?

On a finite 4-connected grid graph, given the source point and destination, it is allowed to consecutively move in one of the four orientions (up, down, left or right) to form a path. We get 1 bonus ...
Rabbiiiiit's user avatar
2 votes
1 answer
96 views

Can Rural Postman Problem with arbitrary start and end be reduced to Rural Postman Problem with single depot node?

Can Rural Postman Problem with arbitrary start and end be reduced to Rural Postman Problem with single depot node? The rural postman problem is: Given a weighted MultiDiGraph $G=(V,E)$, a subset of ...
somewhere's user avatar
0 votes
1 answer
112 views

How to find maximum number of edge-disjoint trails of length $k$ of a directed multi-graph $G=(V,E)$ between arbitrary start and end vertices?

How to find and return the maximum number of edge-disjoint trails of equal length $k$ of a directed weighted multi-graph $G=(V,E)$ between arbitrary start and end vertices? The start and end vertices ...
IsalanOnkar's user avatar
4 votes
2 answers
160 views

Single Source Shortest Path Problem with Multiple Weights Each Edge

I am trying to solve the single source shortest path problem, but with the added constraint that there is an additional weight on each edge (so we have two weights in total for each edge, call them p ...
Daniel's user avatar
  • 149
0 votes
2 answers
62 views

Can negative edge weights in a graph be positive numbers?

I'm a little confused by the concept of a "negative" edge weight. All of the examples I have seen represent negative edge weights as negative numbers. Is it possible for an edge weight to ...
Daniel's user avatar
  • 149
0 votes
1 answer
90 views

How can I track multiple shortest paths from one node to another using Dijkstra / Bellman-Ford

I want to find how many shortest paths are there from Node A to node B. For example, let's say we have a graph with 3 nodes and 3 connections: from 1 to 2 weight 5 from 1 to 3 weight 11 from 2 to 3 ...
ViktorMaksimoski's user avatar
0 votes
0 answers
20 views

Solving a weighted minimum dominating set problem with its unweighted counterpart?

Question Is it possible to find a solution to the weighted minimum dominating set problem, by solving a (related), unweighted minimum dominating set? Elaboration In essence, can one convert a ...
a.t.'s user avatar
  • 123
1 vote
1 answer
176 views

Find a weight threshold for edges for maximum number of connected components in a graph

So the problem starts with a graph in which every node is connected with every node by a weighted edge. The goal is to find a weight treshold W, so that every edge that has a weight lower than or ...
Tomyy's user avatar
  • 25
0 votes
0 answers
50 views

Minimum k-cut with equally weighted sets

I've got a weighted graph $G$, where additionally each vertex has a weight too. For a fixed, given $k$ I am looking for an algorithm to partition $G$ into $k$ disjoint sets of vertices, so that: The ...
kchnkrml's user avatar
1 vote
0 answers
104 views

Topological sort of DAG that minimizes maximum number of unique-source-edges crossing through any node when placed in 1-d line

Consider a DAG such as one shown below: How do I find a particular topological order of nodes, such that when the nodes are placed in a straight line, the maximum number of unique-edges that cross ...
nepee's user avatar
  • 280
0 votes
1 answer
39 views

Which algorithm solves the single-pair shortest path in a weighted directed cyclic graph?

I need to find the shortest path between two nodes in a directed, positively weighted graph that migt contain cycles. All weights are either zero or one. If it was not weighted, I'd use breadth-first ...
Anna's user avatar
  • 3
0 votes
1 answer
81 views

Directed weighted multigraph with dynamic edges - shortest path

I need to create an implementation of a directed weighted multigraph with dynamic edges: The edges will be changing during the pathfinding, in the following way: Summary of the pathfinding: ...
discrete coder's user avatar
0 votes
1 answer
294 views

Find the shortest distance path in a weighted graph, where the weight of each edge is non-negative and less than a constant C = 500 in linear time

The problem is to find the shortest distance in a weighted graph, where the weight of each edge is non-negative and it is given that the weight of each edge is less than a constant C. For example, C = ...
Mikey's user avatar
  • 3
0 votes
1 answer
97 views

find the shortest path between two vertices with Dijkstra (Increase and deacrese wieght one by one)

We have a weighted and undirected graph. I want to find the shortest path between two vertices with Dijkstra algorithm. But in the path, the weight of the edges should be increased and decreased one ...
Amir's user avatar
  • 1
1 vote
1 answer
312 views

Why Prim algorithm may fail to return minimum spanning forest on disconnected undirected graph

I am trying to address the following claim- "running prim algorithm on a disconnected undirected graph returns minimum spanning forest". I thing that the claim may be false (i.e there might ...
DR_2001's user avatar
  • 25
0 votes
1 answer
82 views

Transforming a Travelling Salesman Problem to a Maximum Clique Problem

Say you have a directed graph consisting of n nodes and containing edge weights. A starting node is also given. You want to begin your route at that node and visit each other node in the graph exactly ...
Emily's user avatar
  • 1
0 votes
1 answer
63 views

How sparsity term in loss function for sparse autoencoder is making hidden units inactive?

I am working on a Sparse Autoencoder but Andrew NG's notes are hard to understand. My question is about the following equation: Loss Function. In sparse autoencoder, the goal is to inactive some ...
p200401Samuel's user avatar
-1 votes
1 answer
567 views

How to show that any greedy algorithm gives a 2-approximation for the best min weighted vertex cover

The problem I am trying to solve is that there is an underlying undirected graph G = (V, E) with weights on the vertices, where the weight on vertex ...
ConScience's user avatar
1 vote
3 answers
159 views

Algorithm to find Minimal Spanning Subgraph

I'm attempting to solve this problem: Given an undirected connected graph $G=(V,E)$ with $\mathrm{weight}(e)>0$ for all $e \in E$, and a subset $S \subseteq V$, we define that a sub-graph $H=(V',E')...
Aishgadol's user avatar
  • 317
0 votes
0 answers
25 views

Analyzing Parallel Matching Algorithm - Why it takes O(n+m) time and work?

Using the algorithm provided by this paper, they said that: The algorithm defines a single phase of the local max algorithm. Each step of the phase takes at most O(log(m + n)) = O(logn) time and O(n +...
Reem Aljunaid's user avatar
1 vote
2 answers
75 views

Shortest path algorithm on graphs with non-numerical weights

TL;DR: Floyd-Warshall algorithm seems to also accept "is-a" and "has-a" relationships as edge weights. I want to know exactly why this is fine, and how to generalize this notion of ...
EatChangmyeong's user avatar
1 vote
0 answers
112 views

Longest (weight-wise) walk In a directed graph with weights becoming negative after traversing once

Problem definition I have a directed graph $G = (V,E)$, with positive weights $w(e)>0\:s.t\:\forall e \in E$ I would like to find the longest walk (i.e. edges and nodes may be repeated) in terms ...
sagooz's user avatar
  • 11
0 votes
2 answers
60 views

MInimum Spanning Tree and Combinatorics

I just got a small confusion here, I have a graph for which i need to get number of minimum spanning tree, So, in graph i have 3 edges with weight 2 and 4 edges with weight 3, in such a way that AE = ...
Niraj Jain's user avatar
0 votes
2 answers
175 views

subtract the weight of the largest edge

I have an oriented and weighted graph, and I need to find the cheapest route from source to destination. Now I have a source node A and a destination node B the cheapest path is given to me by the sum ...
ant0982's user avatar
  • 13
2 votes
1 answer
157 views

Minimize max subtree weight among spanning trees

Suppose we have an undirected, connected graph $G$ where vertices have positive integer weights. Let $\bar{v}$ be a given vertex in $G$. Take a spanning tree $T$ of $G$ rooted at $\bar{v}$ and define ...
Andrew's user avatar
  • 287
1 vote
1 answer
157 views

Algorithms for finding closest graph node within set of nodes

Given a set of nodes $N$ on an undirected, weighted graph $G$ and a query node $n$, what is the fastest algorithm for finding the node in $N$ that is closest to $n$? Furthermore, say we are doing many ...
user12878817821's user avatar
-1 votes
1 answer
74 views

Is there an algorithm able to finding the best cost in a graph that is weighted on both vertices and edges?

I have a problem that consists of finding a good solution for a graph that has vertex weights (and this cost is the highest priority), but also has edge costs.
Fernanda's user avatar
-1 votes
1 answer
152 views

Does a minimum spanning tree necessarily provide the lowest cost path between any 2 nodes?

If I'm given a minimum spanning tree, my understanding is that it is a structure that connects all nodes to each other through some path, and that the overall weight of the tree is smallest. However, ...
Jeremy Fisher's user avatar
3 votes
1 answer
117 views

Efficiently determine which nodes should leave a graph while maintaining connectedness

Suppose I have a graph with node weights, where a weight is either -1 or a positive integer. For example: If a node has weight -1, it is "happy", and cannot be kicked out of the graph. If a ...
416E64726577's user avatar
-1 votes
1 answer
31 views

weighted graph separation algorithm proof

I have a graph G (G=(V,E)), where each edge has a non negative weight to it. My problem is to find a subset S (it doesn't have to exist) of nodes such the sum of all the weights of the edges that ...
Johnny13696's user avatar
0 votes
2 answers
398 views

Calculate shortest cycle that contains node $s$

Let $ G(V, E, w)$ be a graph with no negative weights. Describe an algorithm that returns the shortest cycle containing a node $ v $. I came across this algorithm https://courses.engr.illinois.edu/...
Danny Blozrov's user avatar
0 votes
1 answer
152 views

Dynamic routing algorithm

In static routing where the network parameters dont change, we can use Djikstra's or Bellman-Ford's algorithm to find the shortest path to send data from source to destination.However in dynamic ...
Jun Seo-He's user avatar

1
2 3 4 5
8