The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [graphs]

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

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