# Questions tagged [graphs]

Questions about graphs, discrete structures of nodes which are connected by edges. Popular flavors are trees and networks with edge capacity.

3,437 questions
Filter by
Sorted by
Tagged with
18 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$ ...
16 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-...
13 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 ...
11 views

### How do programs like Apache Airflow/ Luigi determine shortest path and how does that relate to graph theory?

I am looking for a simple layman's term explanation on how do programs like Apache Airflow or Luigi (or any Task/ETL schedulers) determine the shortest path to complete a certain task and make it ...
15 views

### How to construct a DFA which accepts all the strings endig with aa and no two consecutive b (bb)

I have to construct a DFA which ends with aa and does not contain any pair of b-s. A = {a,b}, {aa,baa,aaa,abaa,babaa,...}. I know how to construct them as separate DFAs but not together merged.
34 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/...
42 views

### Fastest algorithm for transforming points into graph

Given a set of $n$ two-dimensional points in the plane $$\{ (x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)\}$$ and a real number $M$, I want to transform this set of points into a graph with the points as ...
21 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 ...
40 views

### Is the Clique Problem polynomial time reducible to the graph-Homomorphism Problem and if so what does the reduction look like?

Is the k-Clique Problem (given a Graph G and a natural number k does G kontain a Clique of size k) polynomial time reduzible to the graph-Homomorphism Problem (given two graphs, G and H, is there a ...
68 views

### Clique-problem for planar graph

I have to show, that the clique problem in planar graphs is in P. I found the answer here here. However I don't get the conclusion This follows already from Kuratowski's theorem: a clique is at ...
36 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 ...
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)$ ...
23 views

### Maximising sum of associated elements

I have a set of elements. Each element is connected with every other element by a path of length $l_i,_j\geq0$ (where i$\neq$j). I have to calculate the maximum sum of path length such that I should ...
73 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)$, ...
25 views

### Breadth First Traversal for graph with multiple connected components

I read BFS and DFS from CLRS and realized that the BFS algorithm does not consider graph with multiple connected components but only with single connected component, whereas DFS algorithm considers ...
42 views

### Why does this code return $\frac{count}{2}$ instead of $count$?

I am reading "Algorithms 4th Edition" by Sedgewick & Wayne. The following method computes the number of self loops of an undirected graph $G$. Why does this code return $\frac{count}{2}$ instead ...
25 views

### Prove that there is a sequence of k minimum spaning trees between two distinct minimum spanning trees that each one is different in only 1 edge [duplicate]

I'm pracitcing exams towards finals, Given an undirected graph $G(V,E)$ , we denote 2 MST $T,T'$ neighbours if by deleting one edge from $T$ and add another one we get $T'$. Prove : for every 2 ...
36 views

### Algorithm for breaking a graph into sub-graphs based on an attribute

I am a biologist doing some computational work. I encountered a problem and need some help since I don't have much algorithmic background. The problem: Assume we have a non-directed, weighted graph,...
13 views

### Relation between shape descriptors and featured connected component in matching problems

Hope I'm asking in the correct community, from the title, I need a clarification regarding the idea of dealing with 3d descriptor and featured connected components. I have this approach: model -> ...
372 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 ...
64 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 ...
35 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$ ...
69 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 ...
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 ...
114 views

### Number of executions of the algorithm with probability about graphs

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 ...
217 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 ...
728 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 ...
86 views

### Compute the expected size of an approximation of vertex cover

Consider the following randomized approximation algorithm of vertex cover: Input: A graph G = (V, E). Output: A set $C_G \subseteq V$ a vertex cover of $G$. The algorithm: Set $C_G := \emptyset$. ...
26 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.
28 views

### Dijkstra shortest path yields unintuitive results

Considering the following nodes with edge weights in red, Dijkstra's shortest path algorithm seems to return incorrect results, at least by the definition of the steps on wikipedia. By those rules, ...
535 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 ...
21 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$, ...
24 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 ...