All Questions
Tagged with algorithms graphs
1,614
questions
2
votes
1answer
35 views
Calculate boolean matrix multiplication (BMM) using transitive closure
Let us say I am given an algorithm that calculates the transitive closure of a given graph $G = \{ V, E \}$.
How can I use this algorithm in order to perform the Boolean Matrix Multiplication of two ...
-1
votes
0answers
18 views
Finding an algorithm that after removing k edges we get an acyclic graph [duplicate]
Assuming there's an algorithm that can decide belonging to ACYCLIC in polynomial time. How can I use this algorithm in another algorithm that upon the input of a directed graph and a positive number k,...
0
votes
0answers
25 views
Sliding Puzzle w/ multiple solutions
I am trying to write an algorithm which produces a solution to a modified n by n sliding puzzle (assuming that an end state is reachable from the given start state). The change is as follows: tiles ...
0
votes
1answer
38 views
Obtaining an acyclic graph by removing edges using an algorithm that decides ACYCLIC
i don't understand the following:
If there's an algorithm that can decide ACYCLIC in Polynomial time, then there's an algorithm who returns a set of k edges, so that the graph obtained by deleting ...
0
votes
1answer
31 views
If I have an MST, and I add any edge to create a cycle, will removing the heaviest edge from that cycle result in an MST?
Let's say that I have an MST, $T$. I pick an edge not in $T$ and change its weight, and add it to $T$ to create a cycle. Will removing the heaviest edge from that cycle result in an MST?
MST means ...
3
votes
0answers
77 views
How to extend Bellman-Ford to solve the $k$ shortest path routing?
Browsing the wikipedia I got to this page where it is said:
Finding k shortest paths is possible by extending Dijkstra algorithm or Bellman-Ford algorithm and extend them to find more than one ...
1
vote
1answer
34 views
Determining if match is possible
I have a list of patterns with each pattern containing one or more wildcards. For example:
abc*
a*
...
2
votes
0answers
33 views
Bipartite Planar Graph Isomorphism
I want a hueristic algorithm for the following problem. Here, $V(G)$, $E(G)$ respectively refer to the vertex set and edge set of a graph $G$.
Input: two planar bipartite graphs, $G,H$ and a map $\...
-1
votes
0answers
26 views
Back edge in a DFS Algorithm
I run DFS algorithm on the graph and If the I have 2 options so the order is lexicographic.
As I saw in Wikipedia:
back edges, which point from a node to one of its ancestors
Who are my two ...
1
vote
1answer
48 views
Determine whether there exists a path in a directed acyclic graph that reaches all nodes without revisiting a node
For this I came up with a DFS recursion.
Do DFS from any node and keep doing it until all nodes are Exhausted. I.E. pick the next unvisited node once you cannot keep recursing.
The element with ...
2
votes
1answer
84 views
Find and prove a linear algorithm that identifies all cycles and the length in a graph where each vertex has exactly one outgoing edge
Consider a directed graph on n vertices, where each vertex has exactly
one outgoing edge. This graph consists of a collection of cycles as
well as additional vertices that have paths to the cycles,...
1
vote
1answer
33 views
Minimum number of edges to remove to disconnect two node sets $A$ and $B$ in a directed graph
We have directed graph $G$ (not necessarily a DAG), two disjoint sets $A$, $B$, of vertices.
I need to plan an algorithm returning the minimum number of edges that need to be removed, such that there ...
1
vote
0answers
33 views
Shortest path in directed graph passing thru specific vertices
Given a directed graph $G$, vertices $s$, $t$ and group of vertices $U$, suggest a algorithm returning true if exists shortest path $P$ from $s$ to $t$, such that $P$ contains all $U$ vertices.
The ...
2
votes
1answer
45 views
Finding minimal strongly connected graph
I have this question:
Given a strongly connected and directed graph $G = (V,E)$ with positive weights define $E(t)$ to be the group of edges whose weight is at most $t$. Find an algorithm that ...
3
votes
1answer
50 views
Find all edges of G contained in some MSP
I have the following question in a homework:
Let $G = (V,E)$ be an undirected graph, and let
$$A = \{ e \in E \mid \text{ s.t. exists an MSP $T$ containing } e\}.$$
We were asked to find $A$ in $O(m ...
4
votes
1answer
65 views
Maximum flow on a tripartite graph
I have to solve an assignment problem between $\{1,\dots, N\}$ agents and $\{1,\dots, M\}$ objects, which comes to maximize :
\begin{equation}
\sum_{ij}\beta_{ij}x_{ij}
\end{equation}
where $x_{ij}$ ...
2
votes
0answers
24 views
planar max cut graph with constrains
Given a planar graph $G=(V, E)$
I am looking for a max cut algorithm with the following conditions : some vertices are in one of the partition sets?
Is the algo is still polynomial ?
I mean a ...
1
vote
2answers
65 views
Dijkstra and A* Algorithms: Why is A* faster?
I am learning about Dijkstra's Algorithm and the A* Algorithm and I have manually worked through the graph attached here, which is supposed (I think) to demonstrate that the A* Algorithm is faster ...
1
vote
2answers
78 views
Similarly colored paths in a DAG
Is there an algorithm that can efficiently solve the following question?
Given a directed acyclic graph G with n vertices each assigned a random color from a set of size <= n - 1 colors, a source ...
0
votes
0answers
14 views
How to detect self loop in graph using greedy algorithm if given list of number of degrees
if you are given list of n integers that represents the degree of a graph. How to detect if there self loop in the graph using greedy algorithm.
0
votes
0answers
28 views
Artificial ant colony algorithm for graph
let's assume we have ant at node $1$ and she has $\{2,3,4\}$ vertices. How do I compute which one she choose? I mean if the formula $p_{ij}(k)$ is the probability of $k$-th ant at node $i$ choose $j$ ...
0
votes
1answer
42 views
Given a network flow find if there's a min cut that only one of the given edges lay on it
Given a network flow $G=(V,E)$ with capacity function $C$ source $s$ and hole $t$,
and given 2 edges $e_1 , e_2 $.
Find if there exists a min-cut such that only one of the edges belongs to the min-...
0
votes
0answers
14 views
Count to infinity problem (routing) between unsynchronized stations(tricky)
i was wondering, will count to infinity can occur in the following cases? if so, will it necessarily occur or can the routing tables stabilize themselves?
Distances:
From A to B - 3
from B to C - 4
...
2
votes
1answer
59 views
What is the correct complexity of All paths from Source to Target DFS solution?
The question: "Given a directed, acyclic graph of N nodes. Find all possible paths from node 0 to node N-1, and return them in any order."
The DFS solution is described here. https://leetcode.com/...
0
votes
1answer
22 views
Dominating set in bounded degeneracy and bounded degree graphs
I believe Minimum Dominating Set (MDS) is NP-hard for bounded
degeneracy and their subset bounded degree graphs, but
a paper appear to suggest tractability.
Enumeration of Minimal Dominating Sets and ...
0
votes
0answers
64 views
Boruvka algorithm in Elog(log(V)) complexity
I am trying to implement Boruvka algorithm with the use of fibonacci heaps. My idea is the following:
Since Boruvka's algorithm operates like this:
Input is a connected, weighted and un-directed ...
2
votes
0answers
21 views
Blossom's Algorithm or Maximal Matching [closed]
I am given a complete weighted graph and I need to make pairs among the vertices so that the sum of weights is maximum.
(If I have vertices $v1, v2, v3, v4$ and if I make pairs $(v1,v2)$ and $(v3,v4)$ ...
4
votes
1answer
89 views
Algorithm for finding an irreducible kernel of a DAG in O(V*e) time, where e is number of edges in output
An irreducible kernel is the term used in Handbook of Theoretical Computer Science (HTCS), Volume A "Algorithms and Complexity" in the chapter on graph algorithms. Given a directed graph $G=(V,E)$, ...
9
votes
2answers
396 views
Minimum number of swaps in sorting sequence
Given an array of N integer elements (not necessarily distinct), what is the minimum number of swaps (not necessarily adjacent) needed to sort the array?
I've been struggling with this problem for a ...
1
vote
1answer
68 views
Literature request: Generating all vertex subsets of a graph
I am working in an algorithm which finds a unique maximal independent set of vertices. Then, using this set, one can construct all other vertex subsets. I assume this might have some applications ...
2
votes
0answers
40 views
Proving that the Bellman-Ford algorithm contains negative circuit
Let $D=(V,B), n=|V|$ be a directed graph. Then the graph contains a circuit of negative length from $s$ if and only if $f_n(v) \neq f_{n-1}(v),$ where $v \in V,$ and $f_k(v)=$min$\{l(P)|P$ is an $s-v$ ...
0
votes
0answers
70 views
Prove an estimator
Consider an undirected graph $G=(V,E)$ representing the social network of friendship/trust between students. We would like to form teams of three students that know each other. The question is to ...
4
votes
1answer
122 views
Go from source to destination in 2d matrix with min steps collecting all candies. How to do it?
If we have a 2d matrix of max dimension, 95x95 and we have at max 12 candies placed in some cells. We always start from top left corner(0,0) and we need to reach some given destination (x,y) after ...
-1
votes
1answer
220 views
Proof for clustering in a network of friendship
Consider an undirected graph $G = (V, E)$ representing the social network of friendship/trust between
students. We would like to form teams of three students that know each other. The question
is to ...
1
vote
2answers
748 views
min vertex cover to access k edges in a tree
I need to find the minimum number out of $N$ vertices on a tree with $N-1$ edges, so that at least $K$ edges of that tree are connected to these vertices.
For example, if $N=9$ and $K=6$ and we have ...
0
votes
0answers
29 views
Find a longest path with k vertices in a directed graph
Given a weighted directed acyclic graph $G=(V,E)$, find a path (with $k$ vertices) so that the sum of edge-weights is maximum.
2
votes
0answers
22 views
FPTAS algorithm to find flow at each link for multi commodity flow problem?
Given a graph $G$ and $K$ commodities to route from source to destination. I want to find, what is the maximum beneficial flow for each of the commodities and the relevant paths. I understand the ...
1
vote
1answer
551 views
Derandomization of vertex cover algorithm
I have the following randomized-algorithm for the vertex cover problem. Let $B_0$ be the output set:
Fix some order $e_1, e_2,...,e_m$ over all edges in the edge set E of G, and set $B_0=∅$.
Add to ...
1
vote
1answer
24 views
Dijikstra's algorithm with “hull” value catch
Whilst preparing for the CCC(Canadian Computing Competition), I encountered CCC 2015 Seniors problem 4, linked here.
Anyway, the problem describes a set of vertices(points) numbered from $1$ to $N$, ...
4
votes
0answers
26 views
Strongly connected subgraph that contains no negative cycles
Is there an efficient algorithm that solves the following decision problem:
Given a strongly connected weighted directed graph $G$, defined by its transition matrix, is there a strongly connected ...
1
vote
1answer
164 views
Error lower-bound for an algorithm for vertex cover
I have the following randomized-algorithm for the vertex cover problem. Let $B_0$ be the output set:
Fix some order $e_1, e_2, . . . , e_m$ over all edges in the edge set E of G, and set $B_0 = \...
2
votes
1answer
139 views
Find shortest path of R,G,B Graph
Let $G=(V,E)$ be a directed graph, $ω:E→\mathbb{R}$ a weight function, and $s,t\in V$ a pair of different nodes. It's given that $G$ doesn't have a negative cycle. Each edge has the color R or G or B. ...
2
votes
1answer
28 views
Edmonds-Karp Algorithm with both directed and undirected edges?
How would this work and be implemented?
If you have directed edges pointing away from the source to a bunch of other verticies, and directed edges pointing from those vertices to a sink, but have ...
2
votes
1answer
276 views
O(V+E) algorithm for computing chromatic number X(g) of a graph instead of brute-force?
I came up with this O(V+E) algorithm for calculating the chromatic number X(g) of a graph g represented by an adjacency list:
Initialize an array of integers "colors" with V elements being 1
Using ...
3
votes
1answer
402 views
Shortest paths between given red vertices and arbitrary blue vertices
Given an undirected weighted graph, where each vertex has one of two colors - red or blue. I have to answer queries to find the shortest path between a given red vertex and any blue vertex in the ...
1
vote
1answer
172 views
Counting number of paths between two vertices in a DAG
I need an algorithm that computes the number of paths between two nodes in a DAG (Directed acyclic graph) I need a dynamic porgramming solution if possible.
3
votes
1answer
177 views
find the union of all min cuts of a flow network
I'm trying to solve the following question :
Given a flow network $N = (G=(V,E),c,s,t)$. Let $\mathcal F$ be the set of all minimum cuts. Prove that $\mathcal F$ is closed under intersections and ...
3
votes
2answers
91 views
Coloring an interval graph with weights
I have an interval graph $G=(V,E)$ and a set of colors $C=\{c_1,c_2,...,c_m\}$, when a color $c_i$ is assigned to a vertex $v_j$, we have a score $u_{ij}\geq 0$. The objective is to find a coloring of ...
4
votes
1answer
56 views
Partition into paths in a Directed Acyclic Graphs
I have a directed acyclic graph $G=(V,A)$, I want to cover the vertices of $G$ with a minimum number of paths such that each vertex $v_i$ is covered by $b_i$ different paths.
When $b_i=1$ for all the ...
0
votes
0answers
20 views
edmond karp proof
which contradicts our assumption that ıf $d_f'(s,v)<d_f(s,v)$. We conclude that our
assumption that such a vertex exists is incorrect
I can't comprehend the proof above for edmond karp algorithm ...
