0
votes
0answers
4 views

Max flow along cycles

I have a directed graph, and I want to find the maximal amount of flow that I can send along cycles(loops). Can the standard Ford-Fulkerson approach work, with augmenting paths(cycles in this case), ...
0
votes
0answers
39 views

smaller size approximation to minimum vertex cover

Does there exist a simple approximation to the minimum vertex cover problem that aims to find a smaller (or equal) set to the minimum? Usual algorithms seems to aim to find an approximation such that ...
6
votes
1answer
58 views

Implementing general vertex folding procedure in an undirected graph

I'm implementing the algorithm presented in "Improved Parameterized Upper Bounds for Vertex Cover" paper (PDF). I'm a bit stumped by the General-Fold procedure. ...
3
votes
0answers
39 views

Efficient update to rational flow network?

Once we've computed the max flow in a flow network with integral capacities, we can change one of its edges' capacity by a unit and recompute a maxflow in linear time using BFS. Is there something ...
4
votes
2answers
75 views

Decremental reachability in a grid graph

Consider an $n$ by $n$ grid graph. For example, the following. You can of course reach the top left corner from the bottom right. Now consider the graph dynamically with an arbitrary number of ...
2
votes
0answers
81 views

Fastest algorithm for shortest path with atmost k edges on a DAG with non-negative edge weights?

(Please note, this is not a duplicate to Shortest path with exactly $k$ edges OR Shortest path with a fixed number of edges. What I want is a better algorithm) The problem under consideration is to ...
7
votes
0answers
89 views

Change in the distances in a graph after removal of a node

Given an undirected unweighted graph $G=(V,E)$ and a node $s \in V$, we are looking for a vector $\operatorname{diff}[]$, such that, $$\operatorname{diff}[v] = \sum_{u \in V \setminus \{v\}}{(d^{G ...
2
votes
1answer
23 views

connected components - determining “groups” in Go

I would like to write an analysis of go positions. Part of it requires me to determine the "groups" on the board and count their "liberties". Any Go "position" is a collection of black ...
0
votes
0answers
87 views

Dynamic distance from source in a directed graph (only incremental or only decremental)

At the beginning we have a directed unweighted graph of $n \leq 10^3$ vertices, and $m \leq 10^5$ edges, with some vertex being a source, and we perform updates and queries on it. An update is adding ...
11
votes
2answers
64 views

Enumerate all non-isomorphic graphs of a certain size

I'd like to enumerate all undirected graphs of size $n$, but I only need one instance of each isomorphism class. In other words, I want to enumerate all non-isomorphic (undirected) graphs on $n$ ...
4
votes
1answer
53 views

Algorithm to find most nodes in distinct cycles

I am trying to design a program where people trade objects within a fixed set of objects. They offer a single product, and designate a set of products they are willing to accept for that product. ...
0
votes
1answer
42 views

Why BFS is source vertex specific? [closed]

Take a graph $G=(V,E)$ . As we know both DFS and BFS are graph search algorithms . But why the algorithm for BFS is designed in such a way that it does not cares about the vertices that are not ...
0
votes
1answer
67 views

Can I use breadth-forst search for topological sorting?

Can I use Breadth first Search for finding topological sorting of vertices and strongly connected components in a graph? If yes how can I do that? and If not why not? I tried with a simple acyclic ...
3
votes
1answer
62 views

Bellman-Ford and zero-distance cycle

Problem statement: Given a graph G(V,E) which is not acyclic and may have negative edge weights (and thus may possibly have negative-length cycles), how does one detect if the graph has a zero-length ...
3
votes
2answers
94 views

Pick a subgraph that maximizes the total cost of min-spanning tree among all subgraphs of the same size

There is a complete graph $G$ with $n$ vertices and each edge has a distinct weight. Is there an efficient (not necessarily optimal) algorithm to select $k$ vertices from the graph $G$, such that the ...
2
votes
1answer
33 views

Choice of algorithm for hierarchical clustering for minimizing network communication costs

Suppose I have a large distributed task running on a cluster system where part of the workload is compute bound and part depends on network performance. Data transfer is not completely homogeneous ...
2
votes
0answers
33 views

Stopping condition for goal-directed bidirectional search for shortest path

So I have a graph and need to find shortest path between two points in it. I need1 to do it it using bidirectional search. The bidirectional search should be goal-directed, i.e. A*. So let $l(u,v)$ ...
1
vote
1answer
58 views

Non-Approximate Dynamic All-Pairs Shortest Path algorithm for Undirected, Unweighted Graphs?

I am looking for an algorithm involving adding unweighted edges to an empty, undirected graph (with vertices) and then for each, updating the table of shortest paths. An example is if we have ...
1
vote
1answer
59 views
3
votes
1answer
73 views

Finding independent sets so that all nodes are hit frequently

I have a problem, and I appreciate it if you could share your thoughts. Assume that I have a graph. Assume that I have $k$ iterations. I want to find only one independent set (IS) in the graph in ...
0
votes
1answer
57 views

Use Dijkstra to find negative cycles in a graph [closed]

I will state the problem: Suggest an algorithm that works in $O(|E| + |V|log|V|)$ time that checks if there are negative cycles in a graph. So, I saw the runtime, and I immediately said we need ...
2
votes
1answer
51 views

Finding Kernel in DAG

Let $G=(V,E)$ be a DAG. A subset $A \subseteq V$ is called a kernel if for all $u,v \in A$ $uv \notin E$ and for all $v \in V-A$ there exists an $a \in A$ such that $av \in E$ (note again, this is a ...
3
votes
3answers
134 views

Efficient algorithm to find subgraph

I have a really nasty problem (for me) at hand and I was wishing some of you may know an efficient algorithm to solve it. Thanks to all of you in advance. My problem I have a set of elements (that ...
1
vote
0answers
33 views

Shortest path with min-sum multiplication and Boltzmann distribution

My professor presented a method to find shortest paths using the min-sum multiplication and Boltzmann distribution. He multiplies the adjacency matrix many times and takes the $\beta$ of Boltzmann ...
1
vote
2answers
125 views

Finding shortest path from a node to any node of a particular type [closed]

I have an un-directed, un-weighted graph G.Starting from a given node A, i want to find whether there is a path from A to a node of a certain type .There can be many nodes of that type. The problem is ...
0
votes
2answers
126 views

Maximum length path between any two nodes in a tree with possible negative edge weights

Is there an efficient way to find the longest path between any two nodes in a tree. Given that edges can have negative weights. I know about the diameter problem which finds the longest path in a ...
-1
votes
1answer
36 views

Is finding negative cycle vertices NP complete?

I was trying to find all the negative cycle vertices using the Bellman–Ford algorithm using this paper solution 7.1(b) in $O(V)$ by tracing back the predecessor subgraph.It is also stated in ...
1
vote
2answers
83 views

How can I compute the average weight of an undirected graph?

Given a weighted, undirected graph $G = (V,E)$, how can I compute the average weight of edges? It seems an easy problem (divide the total weight to the number of edges!) but I couldn't manage to find ...
4
votes
1answer
117 views

How to reduce the cost of search based on previous BFS?

I got an unweighted, undirected graph, with $N$ vertices, where each vertex has degree $K$. In my case its a grid with dynamic obstacles. My goal is to output a map, based on given location on the ...
1
vote
1answer
195 views

Checking whether two paths are intersecting in a tree

The problem I have is given a Tree graph , and two paths from u1 to v1 and u2 to v2 where u1,u2,v1,v2 are vertices of the Tree . How efficiently can we check that whether they are vertex disjoint ...
1
vote
1answer
54 views

Bellman-Ford without getting stopped by negative cycles

Let $s$ be the source vertex. In the standard Bellman-Ford algorithm (e.g. the version found in CLRS), when there is a negative cycle reachable form $s$, the algorithm will return that a negative ...
0
votes
1answer
96 views

Floyd–Warshall algorithm on undirected graph

I am referring to the algorithm from the Wikipedia page on the Floyd–Warshall algorithm. In case of undirected graphs should I change the assignment statement inside the ...
2
votes
1answer
22 views

Conditional RB Tree union

Input: 2 RB Trees A B, so that both values in a certain range, so that B's range is smaller than A in both sides. Ex. B's range can be [100...200] and A's range is [0...1000] Output: Unite A and B to ...
1
vote
1answer
35 views

Order of steps in Kosaraju-Sharir

The Wikipedia summary of the Kosaraju-Sharir algorithm is as follows: Let G be a directed graph and S be an empty stack. While S does not contain all vertices. Choose an arbitrary ...
4
votes
3answers
76 views

Create a random graph based on the Degree Distribution and Clustering Coefficient Distribution

I am currently working with a very large Social Network and I want to recreate this graph with a smaller dimension, using the original Degree Distribution and Clustering Coefficient Distribution. The ...
3
votes
1answer
100 views

Shortest even path that goes through a vertex

Given an undirected and connected graph $G=(V,E)$ and two vertices $s,t$ and a vertex $d \in V- \{s,t\}$, we would like to define a legal path as a path from $s$ to $t$, passes through $d$ (at least ...
2
votes
2answers
195 views

The Gas Station Problem - fast implementation

Recently I was asking about the algorithm to solve The Gas Station Problem and I got useful answer. Unfortunately solution with transforming a graph to complete graph and then preparing another one to ...
8
votes
3answers
763 views

Understanding an algorithm for the gas station problem

In the gas station problem we are given $n$ cities $\{ 0, \ldots, n-1 \}$ and roads between them. Each road has length and each city defines price of the fuel. One unit of road costs one unit of fuel. ...
0
votes
2answers
42 views

Given a graph, finding if a node has three adjacents from a node subset $N$

Given a graph $G = (V,E)$, assume that we have two disjoint vertex sets $N = \{n_1, n_2 ...\} \subset V$ and $P = \{p_1, p_2, ...\} \subset V$ such that $N \bigcup P \neq V$. I want to find if there ...
4
votes
1answer
67 views

How to perform local search on simple paths?

I have a local search problem. The set of valid solutions are all the simple paths (i.e. without repeated nodes) from a node $S$ to a node $T$ in a directed graph. The question is: given a current ...
1
vote
3answers
96 views

Can not follow the example for max-flow-min-cut on Wikipedia

This Wikipedia example is very confusing. Its saying the max flow = min cut. But I see the max flow = 9 and the min cut = 7. If not, how does the capacity =min cut here? Which is the max flow min cut ...
0
votes
1answer
30 views

shortest time based on traffic congestion data [closed]

I want to develop one algorithm which can predict shortest time to be taken to go to a destination from a source in a road network based on traffic congestion data. Consider that I have a server ...
2
votes
0answers
62 views

Enumerating all paths through directed graph with loops and splits

I am looking for a way to enumerate all the possible paths between a source and one or more sinks in a directed graph, with loops. Also, some edges must enforce a maximum number of traversals (n), so ...
2
votes
1answer
42 views

Given a complete, weighted and undirected graph $G$, complexity of finding a path with a specific cost

Given a fully connected graph $G$, suppose that we are searching for a simple path $P$ with a specific cost $c$. Is answering to that problem yes or no equivalent to subset-sum problem? What would ...
0
votes
0answers
43 views

Marriage algorithm that maximizes number of pairings

I have a bipartite graph similar to the marriage problem, where there are M males and N females, and a 1:1 matching between males and females is desired (with the remainder of the more populous gender ...
0
votes
1answer
43 views

Recognizing interval graphs--“equivalent intervals”

I was reading a paper for recognizing interval graphs. Here is an excerpt from the paper: Each interval graph has a corresponding interval model in which two intervals overlap if and only if ...
2
votes
2answers
131 views

What is the difference between maximal flow and maximum flow?

What is the difference between maximal flow and maximum flow. I am reading these terms while working on Ford Fulkerson algorithms and they are quite confusing. I tried on internet, but couldn't get a ...
4
votes
1answer
73 views

Construct a digraph given its in-degree and out-degree distribution

Could anyone help me with this algorithmic problem: Given the in and out degrees of a set of vertices, is it possible to determine if there exist a valid graph respecting this constraint? The graph ...
2
votes
2answers
225 views

Minimum path between two vertices passing through a given set exactly once

Suppose I have a source node $S$, destination node $D$ and a set $A$ of intermediate nodes $P_1, P_2, \dots$ in an edge-weighted undirected graph. I want to find the vertex $P_i\in A$ that minimizes ...
3
votes
1answer
604 views

Best solutions to 6 degrees of separation

From purely my knowledge of computer science a simple breadth first search from root A in search of node B, while keeping track of the depth of the tree, would be the most effective way to check ...