0
votes
0answers
26 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
33 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
96 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
35 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
107 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
473 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 ...
2
votes
2answers
39 views

Reconstruct directed graph from list of ancestors for each node

I have a problem that I encountered that boils down to the following: Considered this directed graph I found on Google: I have the following information available to me ...
1
vote
3answers
186 views

Can we test whether two vertices are connected in time linear in the number of nodes?

Consider the problem: Given an undirected graph and two of its vertices, is there a path between them? I often read that this problem can be solved in linear time in the number of vertices! I ...
2
votes
2answers
311 views

If all edges are of equal weight, can one use BFS to obtain a minimal spanning tree?

If given that all edges in a graph $G$ are of equal weight $c$, can one use breadth-first search (BFS) in order to produce a minimal spanning tree in linear time? Intuitively this sounds correct, as ...
1
vote
1answer
19 views

Minimum cut versus sparsest cut? [closed]

My question is that I'm trying to find the sparsest cut in a connected, undirected graph (all weights are = 1). Basically, I am looking trying to find the smallest cut (i.e., number of edges cut since ...
5
votes
1answer
158 views

Algorithm to find diameter of a tree using BFS/DFS. Why does it work?

This link provides an algorithm for finding the diameter of an undirected tree using BFS/DFS. Summarizing: Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from ...
0
votes
1answer
79 views

Prim's Minimum Spanning Tree implementation $O(mn)$ or $O(m+n \log n)$?

I am reading Prim's MST for the first time and wanted to implement the fast version of it . $m$ - The number of edges in the graph $n$ - The number of vertices in the graph Here's the algorithm ...
1
vote
0answers
83 views

Algorithm to determine a minimal cost graph [closed]

I'm trying to solve this problem: Given a collection of cities and the number of commuters between cities, design a network of roads for minimal cost where cost includes the cost of building the ...
3
votes
3answers
96 views

How to implement graph search to solve Sudoku puzzle

My teacher pointed out to us during lectures that we could use Graph Search to help us solve Sudoku puzzles which has left me puzzled . I dont see how this is possible as Graph Search is mostly ...
2
votes
1answer
24 views

Meyniel's theorem + finding a Hamiltonian path for a specific graph family

Let's say we have a directed graph $G = (V, E)$ for which $(v, w) \in E$ and/or $(w,v) \in E$ holds true for all $v, w \in V$. My feeling is that this graph most definitely is Hamiltonian, and I want ...
5
votes
1answer
127 views

Is the algorithm implemented by git bisect optimal?

Let $G$ be a DAG. We know that some nodes in $G$ are "bad", while the others are "good"; a descendant of a bad node is bad while the ancestors of a good node are good. We also know that bad nodes have ...
6
votes
1answer
113 views

Why choose D* over Dijkstra?

I understand the basis of A* as being a derivative of Dijkstra, however, I recently found out about D*. From Wikipedia, I can understand the algorithm. What I do not understand is why I would use D* ...
2
votes
1answer
98 views

Why is determining the size of a maximum independent set or a clique in P?

I read that determining the size of the maximum independent set (and also a clique of maximum size) is in P. The versions that find the actual solution are known to be NP-hard. With respect to ...
1
vote
2answers
71 views

Applications of Depth-First Spanning Tree

I know that depth-first search can be used to produce a depth-first spanning tree, which classifies all edges as tree edges, forward edges, backward edges or cross edges. Are there any algorithms that ...
1
vote
1answer
39 views

Proving the correctness of an algorithm, which computes the connectivity of a directed graph

Let $G=(V,E)$ be a directed graph. The connectivity of a graph is the defined as the cardinality of a smallest separator of $G$. A separator of $G$ is a subset $U$ of $V$, such that $G-U$ is not ...
0
votes
0answers
69 views

Finding shortest path in a graph when edge weights depend on the chosen vertices

Here is my problem: I have a directed weighted graph with a substantial amount of vertices (few thousands), no cycles, in fact, it includes a starting node, a final node and an $m \times n$ grid ...
3
votes
0answers
95 views

Prim's Algorithm - Building the Priority Queue

Suppose we were using a priority queue(PQ) to implement Prim's algorithm. My understanding is that initially the weight of all vertices is set to $\infty$. The weight of the starting vertex is then ...
1
vote
1answer
79 views

Deleting vertices so that largest connected component has at most $n/2$ vertices

I have a question regarding a graph algorithm which is as follows: Given a graph $G = (V,E)$ whose vertices are uniquely labeled $\{1, 2,\dots ,n\}$ we want to determine the smallest integer $k$ such ...
0
votes
1answer
97 views

Does “standard” Dijkstra's algorithm work with bi-directional edges and zero cost edges?

I have been reading about Dijkstra's algorithm and I think I understand it. I followed the algorithm in pseudo-code from Wikipedia, and now I wonder: If my graph is bi-directional and I add each ...
1
vote
2answers
53 views

Finding all paths with lengths in a fixed interval in sparse graphs

What is the most efficient way to find all paths of length M to N in a large sparse graph? Some general information: Graph has 30,000 to 50,000 nodes Average number of edges per node ~ 10 M=4, N=7 ...
2
votes
0answers
37 views

Update SSSPP solution on complete digraph on weight changes

I have a directed graph with $N$ vertices. Every pair of vertices is connected by two edges (one in each direction), and each of these edges has a weight which may be negative. On various occasions ...
12
votes
1answer
294 views

Why does Dijkstra's algorithm fail on a negative weighted graphs?

I know this is probably very basic, I just can't wrap my head around it. We recently studied about Dijkstra's algorithm for finding the shortest path between two vertices on a weighted graph. My ...
5
votes
1answer
254 views

Optimal algorithm to traverse all paths in the order of shortest path

I have to generate all possible paths in a directed, acyclic weighted graph with edge costs. I also have to sort them in order of shortest path. The simplest way that comes to mind is to do a ...
3
votes
1answer
68 views

Most common subset of size $k$

I'm trying to write an algorithm that detects the most common subset of at least size $k$, from a collection of sets. If there are ties for the most common subset, I want the one of them whose size ...
2
votes
4answers
124 views

Converting a digraph to an undirected graph in a reversible way

I am looking for an algorithm to convert a digraph (directed graph) to an undirected graph in a reversible way, ie the digraph should be reconstructable if we are given the undirected graph. I ...
1
vote
1answer
131 views

Kosaraju’s Algorithm - why transpose?

In directed graph, to find strongly connected components why do we have to transpose adjacency matrix (reverses the direction of all edges) if we could use reversed list of nodes by they finishing ...
1
vote
2answers
72 views

Weighted Set covering problem with a fixed number of colors

I have a set of elements U = {1, 2, .... , n} and a set S of k sets whose union form the whole universe. Each of these sets is associated with a cost. I have a fixed number of colors, C = {1 , 2, ... ...
0
votes
0answers
71 views

Hopcroft–Karp algorithm time complexity

In the last 2 paragraphs of the paper about Hopcroft–Karp algorithm to find the maximum cardinality matching in bipartite graph: https://dl.dropboxusercontent.com/u/64823035/04569670.pdf The ...
1
vote
1answer
84 views

Finding edges with minimal weight sum, such that every simple cycle contain at least one edge

Given simple, udirected and connected graph with $n$ verticies. Every edge in this graph has some weight. I have to find (in polynomial time) a set of edges such that : 1.every simple cycle in ...
0
votes
1answer
138 views

Find least probable path in graph

I am working on a special case of the longest path problem. For a cyclic directed graph $G=(V, E)$, where the edge-weights are probability values (i.e., $P(\_) = w(s, q)$ with $s,q \in V$), my aim is ...
0
votes
1answer
72 views

Find a diffrent minimal spanning tree for a graph

For my homework I have a problem that I can't solve and it makes me wonder about 2 different MST: Let $G=(V,E)$ be a graph that has a minimum spanning tree $T$. I want to find another minimum ...
1
vote
0answers
67 views

k-shortest paths

Given a weighted digraph $G=V,E$, and a weight function, $d(u,v)$, one can normally use Dijkstra's algorithm to obtain the shortest path. What I am interested in, is how to obtain the ...
4
votes
2answers
131 views

Equivalence of independent set and set packing

According to Wikipedia, the Independent Set problem is a special case of the Set Packing problem. But, it seems to me that these problems are equivalent. The Independent Set search problem is: given ...
4
votes
2answers
88 views

Path finding under constraints

Let $ G=(V,E) $ be a directed graph with a real weight function $w$ defined on the edges and $ a,b \in V$. Let $\alpha$ denote the minimal weight of all paths from $a$ to $b$ and $\beta$ denote the ...
1
vote
1answer
72 views

Algorithm to use for a TSP variant

What type of algorithm would you suggest me to use for this problem? I want to implement an algorithm that minimize the total distance in a graph (TSP) but for only X nodes. Also, we can go as many ...
1
vote
1answer
125 views

Widest path algorithm steps [closed]

I need to compute the bottleneck shortest paths from s to all vertices of a graph by modifying the Dijkstra’s algorithm. I found this explanation on Wikipedia(Link to Wikipedia) but I would appreciate ...
-2
votes
1answer
131 views

Modifying Dijkstra’s algorithm to favor the path with least amount of edges

I need to modify the Dijkstra's algorithm to get the shortest path in a directed graph and get the one with the least amount of edges if there are equal paths. I am thinking to add another data ...
1
vote
0answers
26 views

fastest way to compute scalar product of an ensemble of vectors

I have an ensemble of points in 3D space, represented by their coordinates $\mathbf{c_i}\equiv(x_i,y_i,z_i)^\top$ . I need to calculate the distance between all these points: $\quad\forall i,j\quad ...
6
votes
2answers
108 views

Peer grading design - choosing a graph, to get accurate rankings/ratings

Background. I am writing some code for semi-automated grading, using peer grading as part of the grading process. Students are given pairs of essays at a time, and the students have a slider to choose ...
3
votes
0answers
70 views

'Stable' multi-dimensional scaling algorithm

I'm looking for a way to position nodes on a 2-dimensional plane in such a way that the distances between the nodes, which are entered exogenously, are represented visually in a way that as good as ...
1
vote
1answer
78 views

Can Floyd-Warshall be used to solve an APSP problem without copying the matrix?

According to CLRS, each iteration of the outermost loop (on $k$) makes a new copy of the adjacency matrix. Is it safe not to copy the matrix on every iteration? What I mean is, according to CLRS: ...
0
votes
1answer
104 views

single algorithm to work on both directed and undirected graph to detect cycles?

I have been trying to implement an algorithm to detect cycles (probably how many of them) in a directed and undirected graph. That is the code should apply for both ...
0
votes
0answers
34 views

Efficient way to merge a set of Trails (sequence of nodes in a Graph)

I am trying to come up with a good algorithm to merge a set of Trails. I have described what is meant by a Trail and the conditions which determine if the merge is good or bad. Trail - Linear ...
0
votes
2answers
194 views

Dijktra algorithm vs breath first search for shortest path in graph

I have asked this question in StackOverflow. I was asked to move in here. so here it is: I need some clarifications and inputts regarding Dijktra's algorithm vs ...
3
votes
0answers
81 views

Finding Shortest Paths of weighted graph using stacks

I will be given some kind of this graph as in the picture below. I've searched some algorithms but it seams as if it is something impossible for me to figure them out. In fact using Floyd–Warshall ...