Questions tagged [graphs]
Questions about graphs, discrete structures of nodes which are connected by edges. Popular flavors are trees and networks with edge capacity.
2,303
questions
-1
votes
0answers
15 views
Show that the de Bruijn graph G6,10 is strongly connected and balanced
I've been given this question and have absolutely no idea how to answer it. I can't even find the G6,10 graph nor have I been given it.
1
vote
1answer
15 views
Grokking pseudo-code for solution to gas station problem
I'm trying to grok the pseudo-code for the gas station problem (which I think we should start calling the charging station problem but that's a different story) given as Fill-Row in Fig. 1 in To Fill ...
0
votes
1answer
41 views
binomial tree number of nodes
Does anybody knows that how we can assign number to nodes for binomial tree . I mean how we can represent the number of nodes by array? please give me hint I am really confused .
2
votes
1answer
30 views
How to deal with parallel edges between two vertices in cycle detection using BFS in an undirected graph?
I am new to Programming and learning Algorithms and was studying BFS when I read that BFS could be used for cycle detection. I tried to implement the same on an undirected graph G with Adjacency List ...
1
vote
2answers
37 views
Find the minimal tank capacity to be able to travel from any city to any other
There are $n$ cities in the country. The car can go from any city $u$ to city $v$, On this road it spends $w_{u,v} > 0$ fuel. At the same $w_{u,v}$ can differ from $w_{v, u}$. The task is to find ...
4
votes
1answer
37 views
Modifies Dijkstra’s Algorithm to find the maximum cost path
In a DAG and all weights are larger than 0. Is it possible to use a max heap to get the maximum cost?
2
votes
1answer
22 views
Existence of d-regular subgraphs in a k-regular graph
The claim is as follows:
Let's say we have a $k$-regular simple undirected graph $G$ on $n$ vertices. Then, does $G$ then always have a $d$-factor for all $d$ satisfying $1 \le d \lt k$ and $dn$ being ...
1
vote
0answers
34 views
coloring of an interval graph with constraints
Given an interval graph that represents a set of tasks, in a given period of time, to be assigned to a set of employees, the objective is to find a minimum coloring of this graph such that the total ...
0
votes
0answers
10 views
Separate overlapping clusters
Suppose I have multiple data points in 2d (x,y) that are either labeled as A, B, C, or D. I find a minimum bounding area for points that are labeled as A and refer to it as cluster A. I can do the ...
1
vote
1answer
49 views
How to encode reachability in a graph with walls as a SAT problem
Suppose we have a graph that represents a grid of cells. We are given a cell to start in and a cell that's the destination. There are cells that we cannot enter and they are known as walls. Finally we ...
3
votes
2answers
50 views
Finding a Hamiltonian path in this graph family
Given a directed graph $G = (V, E)$, you have been told that a Hamiltonian path $p_0p_1\ldots p_V$ exists with the property that for each edge $p_ip_j$ that is not part of the Hamiltonian path, $i >...
2
votes
0answers
94 views
How to query the tree?
I encountered an interesting problem based on tree-data-structure.
We are given a tree which has N nodes, with 1≤N≤105.
Time starts from second 1 and it continues for q seconds.
At each ...
1
vote
1answer
35 views
How does the slow All-pairs-shortest-paths algorithm work?
I am trying to fully understand the following algorithm from CLRS book:
I like to think that it works similarly to Bellman-Ford algorithm by relaxing all edges once for every vertex in the graph. ...
0
votes
1answer
43 views
Recursive algorithm for finding a common ancestor between two nodes in a tree, if it exists?
Here's the start and the vernacular I'm using.
...
0
votes
0answers
18 views
Detecting whether a node belong to a cutset with the least memory consumption as possible
I'm working on a problem about connected components implemented by cutsets.
Given a cutset, I want to determine whether some node lies within the connected component created by such cutset. The most ...
-1
votes
0answers
47 views
intervals in geometrical points in 2D space
Can anyone help me and provide me a link for learning geometrical points in 2d space which is related to algorithmic course ? this is the question but as I searched youtube there should be an equation ...
0
votes
0answers
17 views
Graph neural network
I'm trying to build GNN model that classify images , the first step is to model each image with graph , each node represents one pixel , now how can I define the edges in my case ? does the spatial ...
0
votes
0answers
67 views
FInd a graph on a vertex set similar to another graph
I am looking for a possible algorithmic solution to this problem, but I can't figure out any.
Let's say I have a weighted graph (call it G); each vertex on this graph represents a point in a plane, ...
1
vote
1answer
22 views
Directed graph reachability
Given a directed graph G(V,E) and a node s, how do we determine what nodes are reachable from s? Do I need simple traversal algorithms or do I need to look at Tarjan's algorithm?
-1
votes
1answer
56 views
question about algorithm
as you know we have equivalent condition for graphs so I want to ask a very basic question and please help me what is exactly w1(e1) and w1(e2) and w2(e1) and w2(e1) ?
If e1 means path from A to B so ...
1
vote
1answer
51 views
Give an example of a connected graph where α(G) =100 and β(G) = 200
So I need to find a form of a graph such that its vertex cover is twice that of its matching, but I am running into problems brainstorming, I know K3 is of this form, but not one at such a magnitude.
4
votes
0answers
50 views
Acyclic Manhattan turtle
There is a grammar that describes the walks of a turtle around Manhattan, such that the turtle
always returns home. It is described in the book "Parsing Techniques" by Dick Grune and Ceriel
J.H. ...
0
votes
1answer
27 views
Strongly connected graph proof
Here I have a proof related to strongly connected graph from Algorithms book.
However, when I run DFS on the following 2 strongrly connected graph, I get different result than the proof.
According ...
1
vote
1answer
51 views
The optimized numbers of variables and clauses to encode a graph coloring problem in CNF
Problem Statement
Given a finite graph $G = \langle V, E\rangle$, consisting of vertice set $V$ and edge set $E$, and a finite set of colors $C$, a problem instance of graph coloring is to assign ...
2
votes
1answer
94 views
Minimum-cut with minimum number of edges
I am sure many folks here know the famous min-cut max-flow theorem - the capacity of the minimum cut is equal to the maximum flow from a given source, s, to a given sink, t, in a graph.
Firstly, let'...
4
votes
3answers
76 views
Simple cycles of length two in an undirected graph
Pedagogical question.
Background
A cycle in a graph can be defined as a sequence of vertices $v_1,\dots,v_n$ with $v_1=v_n$ such that, for each $i \in \{1,\dots,n-1\}$, the graph has an edge $(v_i,...
1
vote
1answer
29 views
Sorting algorithm for set of elements, when I have comparison of just some pairs not all of them
Is there some kind of algorithm for sorting of set, when there is comparison of just some pairs?
Example 1:
set(a, b, c, d, e)
pairs(a>b, ce)
Example 2:
set(a, b, c, d, e)
pairs(a>b, d>b, c>d, d>e)...
0
votes
1answer
25 views
Efficient algorithm for assigning weights to nodes in graph to create steady state flow
I'm looking for an efficient algorithm (at least polynomial in the size of the graph, preferably linear) for the following problem:
Definitions:
Given a graph $(V,E)$, with non-negative weights ...
2
votes
0answers
17 views
Maintaining SCCs in directed graphs (on-line, under edge deletion) with ES-trees
I'm interested in efficiently maintaining the set of strongly connected components (SCC) in a directed (unweighted) graph under edge deletions only. While searching for ways I came across an article [...
1
vote
0answers
32 views
About Steiner tree problem in graphs
In the
paper (p. 3)
and the
slides
presents the formulation of the Steiner problem on graphs
via so called Steiner cuts.
But according to the definition, the number of Steiner cuts and so the ...
2
votes
1answer
26 views
Another vertex cover question?
I'm not sure this is equivalent to bipartite vertex cover question. The question is:
Given a BIPARTITE graph, what is the minimum number of vertex from the right side whose edges cover all vertex ...
0
votes
1answer
31 views
Unique property of a full binary tree
I read a statement that was unclear to me, and was hoping to get some clarification.
It said that given a full binary tree with $n > 2$ leaves, there exists some internal node such that one third ...
-1
votes
0answers
26 views
Algorithm for matching couriers to orders in a city
I have a problem that bothers me for a long time and could not find the best approach to it yet.
I hope this is the best place to put this kind of question. If not please direct me to a better place :...
5
votes
2answers
1k views
How is the problem, {⟨G⟩|G has no triangle} in Logspace?
I read this problem as a part of my course curriculum, in my professor's notes. I am not able to understand about the standard solution, that if I list all the possible triplets of vertices as 3-...
0
votes
0answers
17 views
O(n) algorithm for the connected components at most n/2 problem [duplicate]
I'm given a problem statement which states
"There always exists a vertex from a tree G such that the remaining connected components have size at most |V(G)|/2".
I'm trying to formulate an efficient ...
1
vote
1answer
35 views
I came up with a way to modify Dijkstra's Algorithm to handle graphs with negative edge weighs [duplicate]
Add a constant $c\geq |w_{min}|$ to each edge of $G$, so that each edge now has non-negative weight.
Run Dijkstra's algorithm
Can anyone tell me if this is viable or if it fails?
2
votes
0answers
22 views
Computing similarity of two graphs with partially overlapping sets of nodes
Consider two graphs $G_1 = (E_1, V_1) $ and $G_2 = (E_2, V_2)$ with their associated sets of edges $E$ and nodes $V$. I'm familiar with concepts such as edit distance for computing the similarity/...
0
votes
1answer
16 views
How do we determine whether a heuristic is better than another in A* search Algorithm?
I am trying to solve a Maze puzzle using the A* algorithm. I am trying to analyze the algorithm based on different applicable heuristics.
Currently, I explored Manhattan and Euclidean distances. ...
0
votes
0answers
27 views
Minimise the maximum degree of a vertex in a connected graph
Given $N$ vertices and $M$ edges, how to create a connected graph so that I can minimize the maximum degree of every vertex. A vertex can have at most degree $N$ (self loop and other $N-1$ edges). ...
1
vote
0answers
66 views
Minimum path cover in a DAG
Given a directed acyclic graph $G=(V,A)$ and a set $A'$ of $A$. It is well known that searching for a minimum number of vertex-disjoint paths that cover all the vertices of $G$ can be solved in ...
2
votes
1answer
28 views
Finding partition with maximum number of edges between sets
Given a graph (say in adjacency list form), is there an algorithm to find a partition of vertices such that the number of edges between the two sets of the partition is the maximum possible?
For ...
2
votes
1answer
34 views
Why does Bellman-Ford algorithm use < rather than ≤?
The Bellman-Ford Algorithm uses a less-than symbol rather than a less-than-or-equal-to symbol. How does this identify that there is a negative cycle?
For instance, say I have the below example going ...
3
votes
1answer
69 views
Algorithm to find a simple path with maximum weight less than a constant in DAG
Given a weighted directed acyclic graph $G=(V,E,W)$, where the weights are non-negative and are on the vertices. I am searching for a simple path of maximum total weight, but this total weight should ...
0
votes
0answers
18 views
Why is BFS “vertex based” and DFS “edge based”?
I am trying to understand the various differences between Breadth-first and Depth-first search on graphs. Two sources state that BFS is "vertex based" and DFS is "edge based" even though in ...
3
votes
1answer
114 views
Minimum Path cover in a Directed Acyclic Graph
Given a weighted directed acyclic graph $G=(V,D,W)$ and a set of arcs $D'$ of $D$, where the weights of $W$ are on the vertices. The problem is to partition $G$ into a minimum number of vertex-...
1
vote
0answers
16 views
Compiler implement power method with syntax graph
We learn how to write compiler. I know that we can use grammar to construct a parser for compiler or otherwise use a syntax graph to represent grammar and generate code when move on it's node. our ...
0
votes
0answers
44 views
Verifying the minimum cost from each node to a sink node in linear time
Problem Statement:
Let $G= (V, E)$ be a directed graph with costs $c_e \in \mathbb{R}$ on each edge $e \in E$. There are no negative cycles in $G$. Suppose there is a sink node $t \in V$, and for ...
3
votes
1answer
49 views
Forward edges in undirected graph using BFS
Introduction to Algorithms books claims BFS only classifies an edge for an undirected graph to be either tree or cross edge. But how about this simple example below where forward edges are naturally ...
0
votes
1answer
62 views
how to prove correctness of this BFS algorithm?
Given an undirected connected graph, I wrote the following algorithm based on BFS. The algorithm detects wether this graph contains a cycle. If it contains a cycle then prints it. I'm pretty sure that ...
0
votes
0answers
18 views
Two algorithms for finding bridges in a graph that are almost the same
So I'm looking at an algorithm for finding bridges in an undirected graph. The thing is, there is a version of this algorithm that I've used so far that looks like this (C++)
...
