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
0
votes
0answers
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$ ...
-1
votes
0answers
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-...
0
votes
0answers
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
...
0
votes
0answers
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 ...
1
vote
1answer
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.
2
votes
1answer
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/...
3
votes
1answer
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 ...
0
votes
1answer
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 ...
2
votes
1answer
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 ...
1
vote
2answers
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 ...
0
votes
0answers
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 ...
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)$ ...
0
votes
0answers
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 ...
4
votes
1answer
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)$, ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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,...
0
votes
0answers
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 -> ...
8
votes
2answers
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 ...
1
vote
1answer
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 ...
2
votes
0answers
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$ ...
0
votes
0answers
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 ...
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
0answers
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 ...
-1
votes
1answer
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 ...
1
vote
2answers
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 ...
8
votes
0answers
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$.
...
0
votes
0answers
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.
1
vote
1answer
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, ...
1
vote
1answer
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 ...
1
vote
1answer
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$, ...
4
votes
0answers
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 ...
2
votes
0answers
29 views
Disjoint paths in digraphs is NP-complete
In the article:
S. Fortune, J. Hopcroft, J. Wyllie, The directed subgraphs homeomorphism problem, Theoret. Comput. Sci. 10 (1980) 111–121.
link:
https://www.sciencedirect.com/science/article/pii/...
1
vote
1answer
162 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 = \...
0
votes
0answers
9 views
What are RDF graphs and OWLs commonly used for?
Not sure if this is the right site, but I'll give it a go.
I find the concept of the Semantic Web fascinating, and the idea of using RDF triples to represent semantic data. But obviously the vision ...
3
votes
1answer
125 views
maximum coverage version of dominating set
The dominating set problem is :
Given an $n$ vertex graph $G=(V,E)$, find a set $S(\subseteq V)$ such that $|N[S]|$ is exactly $n$, where $$N[S] := \{x~ | \text{ either $x$ or a neighbor of $x$ ...
4
votes
2answers
29 views
Complexity of list coloring $K_n$ with $n$ colors
The list coloring problem is, given a set $L(v)$ colors for each vertex $v \in G$, is there a proper vertex coloring, $c$, of $G$, such that $c(v) \in L(v), \forall v$.
I was wondering, for complete ...
5
votes
1answer
161 views
How hard is finding the shortest path in a graph matching a given regular language?
Suppose we are given a directed graph $G = (V, E)$ with edge weights $w : E \rightarrow \mathbb{R}$ (we can assume there are no negative cycles) and edge labels $\ell : E \rightarrow \Sigma$ from some ...
2
votes
1answer
104 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
0answers
34 views
Finding Minimum Weight Subgraph with k Vertices
Assume a complete graph G={V,E} that has n vertices and $C_{n}^{2}$ edges, and the weights of E are all positive. I am trying to find a complete subgraph containing k vertices, and it has the maximum ...
2
votes
1answer
32 views
Max flow algorithm for floating-point weights and E~=10*V
Could you, please, suggest a maximum flow algorithm for a graph with floating-point weights and the number of edges approximately equal to the number of vertices? I.e. ...
2
votes
1answer
21 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
271 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 ...
0
votes
0answers
24 views
Deadlock in resource allocation graph
I am unsure if there is a deadlock in this particular graph.
Not sure if P2 and R2 make a cycle.
As well as P2 - R3 - P1 - R1 - P2. It seems there is a cycle, but not sure if there is a deadlock ...
8
votes
2answers
764 views
Length of strings accepted by DFA
Problem: Given a DFA $D$, find all possible lengths of strings accepted by the $D$.
It makes sense that these lengths can be represented as $a_i+kb_i$. What might be the algorithm to find all such ...
3
votes
1answer
379 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
126 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
157 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
86 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 ...
