All Questions

Tagged with
Filter by
Sorted by
Tagged with
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 ...

1 2 3 4 5 33