Questions tagged [weighted-graphs]

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

110 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
12 votes
0 answers
920 views

Optimal meeting point in directed graph

Let $G(V, E)$ be a edge-weighted directed connected graph and $v_1, \dots, v_n \in V$ be some vertices. Let $d(a, b)$ denote the length of the shortest path from $a$ to $b$, for $a,b \in V$. I need ...
vojta's user avatar
  • 221
10 votes
0 answers
236 views

Minimum edge deletion partitioning of a planar graph

I'm interested in the time complexity of the following problem: Given an undirected planar graph $G=(V,E)$ and a weight function $w:E \rightarrow \mathbb{Z}$ (so weights can be negative, too), color ...
EmreA's user avatar
  • 153
7 votes
0 answers
447 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 ...
Saar BK's user avatar
  • 55
5 votes
0 answers
774 views

Faster maximum weight matching algorithm in bipartite graph

I need to do a maximum weight matching in bipartite graphs rather than maximum weight perfect matching (which means that there is no need to match all the nodes). The nodes each side are both (at ...
Kaho Chan's user avatar
  • 161
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
4 votes
0 answers
60 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 ...
Mu-Tsun Tsai's user avatar
4 votes
0 answers
86 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, ...
Janek's user avatar
  • 41
4 votes
0 answers
386 views

Is there a relationship between graph entropy and node entropy?

Eagle, et al [1] discuss the notion of node entropy and this is captured in igraph via the diversity metric. I was wondering if there was any relationship between these node entropies and the idea of ...
Aengus's user avatar
  • 141
3 votes
0 answers
86 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 ...
Rajarshi basu's user avatar
3 votes
0 answers
186 views

Time taken by virus to reach all nodes

Given a connected graph, with weighted edges, a virus starts from a given node. It takes x seconds for the virus to travel from a node to one of its neighbours where x is directly proportional to the ...
Ayush Goel's user avatar
3 votes
0 answers
305 views

Dynamic all pairs shortest path edge removal

I have a planar(|E|=O(V)) undirected graph with positive edge weights. I have already calculated all pairs shortest path with Floyd–Warshall algorithm. Now I want to recalculate APSP with an edge ...
Separius's user avatar
  • 131
3 votes
0 answers
147 views

Assignment problem with symmetric matrix

I came across a problem which I think can be reduced to the assignment problem/Hungarian algorithm. We have matrix $A$ and matrix $B$ which are both $n\times n$ symmetric matrices. We can rearrange $...
user89692's user avatar
3 votes
0 answers
188 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 ...
Paul Accisano's user avatar
3 votes
0 answers
378 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 ...
niloofar jamshidi's user avatar
3 votes
0 answers
178 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 $\...
T.Harish's user avatar
  • 222
3 votes
0 answers
90 views

Algorithm for finding the set of minimum coordinate pairs

Consider these two sets of coordinate pairs with weights: ...
user1658296's user avatar
3 votes
0 answers
440 views

Assigning edge weights under shortest path constraints

We are given a graph $G = (V,E)$ and we need to find an assignment of non-negative edge weights (You must give every edge a non-negative weight). We are also given a set $R\subseteq V$ and mapping $c_{...
user3494047's user avatar
3 votes
0 answers
4k views

Applications of min spanning trees

What are the significant applications of minimum spanning trees? After doing some research online and in several textbooks, I have found three real-world applications: Building a connected network. ...
D.W.'s user avatar
  • 158k
3 votes
0 answers
358 views

What is a semantic cognitive map

Based on: J. P. Carvalho, "On the Semantics and the Use of Fuzzy Cognitive Maps in Social Sciences" (WCCI, 2010 -- PDF) and Richard Dagan's web page Cognitive Mapping. A cognitive map consists of ...
Ria George's user avatar
2 votes
0 answers
77 views

Translating weighted regular expressions with the complement operator to weighted deterministic automata

I want to implement regexp search via translation to deterministic automata, as a toy project. TLDR: how to combine the extended regular expressions with the weighted regular expressions, with the ...
user2373145's user avatar
2 votes
0 answers
70 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 a degree of $1$ internal ...
user157116's user avatar
2 votes
1 answer
388 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 ...
curiouscupcake's user avatar
2 votes
0 answers
95 views

Minimum Product Weight in a Graph with 2 weight functions

Hello Community, Given an undirected graph G = (V,E) where E has 2 weight functions w1(e) --> {1,2,..9} and w2(e) --> {1,2...9} with given a source vertex s and destination vertex t. we can ...
anony_std's user avatar
2 votes
0 answers
73 views

Total weight of all spanning trees

Given a weighted simple undirected connected graph $G = (V, E, w:E \to \mathbb{R})$, let $\tau(G)$ be the set of all its spanning trees. Is there an efficient algorithm to determine or estimate with ...
abhi01nat's user avatar
  • 141
2 votes
0 answers
73 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 ...
Trung's user avatar
  • 21
2 votes
0 answers
26 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 ...
mo2019's user avatar
  • 379
2 votes
0 answers
421 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 ...
Ago's user avatar
  • 121
2 votes
0 answers
559 views

Online version of bellman-ford algorithm?

Suppose I have a graph on which I've run the Bellman-Ford algorithm. Now I change the weight of subset of edges. Is there an efficient way to re-run the algorithm without having to completely start ...
Thomas Johnson's user avatar
2 votes
0 answers
564 views

Bhandari Algorithm: Canceling Edges

I have a quick question on implementing the Bhandari algorithm. I do not have the textbook where the algorithm is originally given (Bhandari, Ramesh (1999). Survivable networks: algorithms for ...
armstrhu's user avatar
  • 121
2 votes
0 answers
53 views

Bus stops problem

I have the following problem I need to solve, and I hope you can point me to the right direction. I have a bunch (4000) of people addresses in a city that are mapped to coordinates (longitude and ...
acertijo4ever's user avatar
2 votes
0 answers
154 views

Multicommodity shortest path problem on a directed acyclic graph

I have n commodities with each a unique source and sink node. Each source-sink pair is connected in some manner on a directed acyclic graph. All arc weights are non-negative. The goal is to find the ...
Charles's user avatar
  • 21
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
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
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
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
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
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 vote
0 answers
280 views

Clash Royale Algorithm for troops path

I am making a clone of Clash Royale which is basically a Tower Defence game. As you can see from the picture you can deploy different troops only in your side of the court (that blue rectangle), and ...
panini's user avatar
  • 19
1 vote
0 answers
17 views

Aggregating pairwise ratings in a graph

A finite set of individuals provide bounded non-binary pairwise ratings of other individuals (say, -10 to +10), forming a directed graph (cycles possible). I'd like to determine aggregate ratings for ...
vsekhar's user avatar
  • 111
1 vote
0 answers
50 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 ...
samleo's user avatar
  • 11
1 vote
0 answers
55 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 ...
IDK's user avatar
  • 111
1 vote
0 answers
44 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 ...
de1's user avatar
  • 111
1 vote
0 answers
602 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 ...
AsaridBeck91's user avatar
1 vote
0 answers
59 views

Finding path with best distance/cost ratio from a node in a graph

We have a weighted graph, where each node is a city. And the edges between the nodes are a pair of floating-point values (distance and cost of travel). Given a node/city, describe an algorithm that ...
zemageht's user avatar
1 vote
0 answers
41 views

Finding a cut maximizing average weight of cut edges

Just checking if this version of Max Cut is still NP-hard: Given a fully connected graph $G(V,E)$, where every vertex is connected to every other vertex, and where every edge has a weight associated ...
DBrons's user avatar
  • 13
1 vote
0 answers
84 views

"Second order" widest path problem

Let's say we have a directed graph in which each pair of adjacent edges has a weight; or, alternatively, each ordered triple of vertices A, B, C has a weight $W(A,B,C)$ of going A->B->C. I am ...
mmm's user avatar
  • 41
1 vote
0 answers
20 views

finding common navigational paths / central nodes within a graph

I have a directed weighted graph representing street (edges weighted by distance) and street intersections (nodes). Using this graph, I would like find central nodes that a person might find ...
alacarter's user avatar
  • 111
1 vote
0 answers
21 views

Number of graphs that satisfies the property that edge weight is maximum of node values on which the edge is incident

I have an undirected weighted graph without multi edges. All the edge weights are whole numbers and known. I want to know in how many ways node values(node values are also whole numbers) can be ...
Siddharth Mishra's user avatar
1 vote
0 answers
37 views

Floyd's Algorithm with a negative cycle

I know that I cannot use Floyd's algorithm if I have a graph with at least one negative cycle, because path-lengths between vertices can be arbitrarily small. I am wondering, how the distance ...
I love math's user avatar