Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [graphs]

Questions about graphs, discrete structures of nodes which are connected by edges, including trees and graphs with weighted edges.

Filter by
Sorted by
Tagged with
1 vote
0 answers
34 views

Understanding line in Ramsey's Theorem proof

The following is from lecture notes for Concepts in Mathematics from CMU (William Gunther): I am confused about the bolded sentence in the last line quoted here: Theorem 4 (Ramsey's Theorem). For any ...
Flying Spaghetti's user avatar
0 votes
1 answer
36 views

Understanding the last algebra step of this proof

Could someone help me understand why in the below proof, if $k > log_{2}n$, then $P(N_i=1)< \frac{1}{n}$?
Flying Spaghetti's user avatar
1 vote
1 answer
92 views

Running time of modified BFS algorithm to find shortest path in weighted DAG

While the shortest path can be calculated with $O(V+E)$ time over a weighted directed acyclic graph using topological sort, I wonder about the running time of the following BFS type algorithm I ...
wsz_fantasy's user avatar
1 vote
0 answers
25 views

CHK graph dominance algorithm proof

The algorithm developed by Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy is widely used in industry for building dominator tree, but I cannot follow the proof in the “Engineering the data ...
rand0m_scr1pt_k1dd1e's user avatar
1 vote
0 answers
31 views

Understanding Arc Consistency 4 in the context of Wave Function Collapse

Following this blog post about the Arc Consistency algorithms. Namely, the explanation on AC4. Consider the following example: If I understand AC problems correctly. Then: We have two known ...
bli00's user avatar
  • 111
0 votes
0 answers
28 views

Distance to specific node incremental addition

Let us say I have an empty graph G and a list of nodes N to add to the graph one-by-one. Let us say that I will have a node <...
OlorinIstari's user avatar
0 votes
0 answers
20 views

flow network, class and classroom matching

Problem: given a set of classes and classrooms, then given a set M of pairs (a,b), which means it is valid assignment from class a to classroom b(ex:(c,2), (c,3), (d,2), means class c can be assigned ...
Joseph Ritcher's user avatar
1 vote
0 answers
24 views

Mapping a grammar to a graph - Relation of Terminal Symbol and Node Coverage in Software Testing

I am currently trying map a grammar to a graph in the context of syntax- and graph-based testing. However, until now I haven't had an enlightenment how would I map non-terminals and terminals to nodes ...
Daraan's user avatar
  • 111
4 votes
1 answer
25 views

Name of graph family defined by modular sum

In the context of finite, simple, undirected graphs, associate with each node $v\in V$ an integer $n(v)$ (you can limit this to positive integers without loss of generality). Create the set of edges ...
JimN's user avatar
  • 849
9 votes
1 answer
166 views

Can we solve $\mathrm{MFVS} \leq 1$ in linear (or subquadratic) time?

$\mathrm{MFVS} \leq 1$ is a concise way of writing the following decision problem: Let $G = (V, E)$ be a directed graph. Is there a $v \in V$ such that every cycle in $G$ passes through $v$? (More ...
Mees de Vries's user avatar
2 votes
1 answer
88 views

Optimal graph data structure for set of points that allows dynamic updates

We aim to optimize the execution of a specific task. Consider a set, P, containing N 2D points. A new query point, p1, is introduced, and the objective is to identify the nearest point in P to p1. If ...
Apurv Mishra's user avatar
1 vote
1 answer
57 views

Choose edges in fully connected weighted graph that minimize sum of weights

I was looking at the Advent of Code 2023 day 11 problem and misread it to think that the question ended up asking something akin to what's below (after transforming the positions of the "galaxies&...
Orion Yeung's user avatar
1 vote
1 answer
115 views

number of edges that appeared at least in one shortest path

In a simple weighted graph, with n vertices and m edges , for each pair of vertices we want to find the number of edges that appeared at least in one of the shortest paths between these two vertices. ...
mostamele's user avatar
1 vote
0 answers
60 views

Assumption on SuccessiveShortestPaths

I read that one assumption for Successive Shortest Paths algorithm for computing the minimum cost flow problem is that every cost is non-negative. I also read that this assumption can be removed with ...
Wuac's user avatar
  • 31
0 votes
0 answers
22 views

Placement of Tasks from Dataflow Graph on a Physical Graph

I have a dataflow graph where a set of different types of tasks are placed in corresponding types of nodes. Say the task types are called A, B, and C. A-type tasks are placed in all the leaf nodes of ...
bsha's user avatar
  • 1
2 votes
1 answer
61 views

Non-dominated maximal paths in a DAG

Let $D(V, A)$ be a DAG. We call a dominated path in $D$ a path $P$ such that $P$ is maximal and $\exists P^{'} \in D . (P^{'} \text{ is maximal } \wedge V(P) \subset V(P^{'}))$ that is, $P$ is a ...
Matheus Diógenes Andrade's user avatar
0 votes
0 answers
38 views

Amortized analysis on skew heap arbitrary deletion

A practice problem in my textbook asks to proof the amortized complexity for a sequence of insert, delete min, and decrease-key operations on an initially empty skew heap. Insert and delete min both ...
Tomyy's user avatar
  • 25
0 votes
0 answers
13 views

Identifying peaks at every cluster

I have a data set showing different clusters of data points and was attempting to find a way to get the peak of at every cluster. Comparing the moving average between a set of points does not work as ...
Nader's user avatar
  • 101
0 votes
0 answers
34 views

Dynamic Program to find well formed set in a rooted tree

You are given a rooted tree $T=(V,E)$ with $n$ nodes and the root $r$. Each node $u\in V$ has an integer label $l(u)$. Suppose $S⊆V$ then $S$ is well-formed if for every $u,v\in S$ if $u$ is an ...
Sooraj S's user avatar
  • 139
1 vote
0 answers
244 views

The second shortest path on a directed graph [closed]

The question asks to write an algorithm using Dijkstra's algorithm with time complexity of $\Theta(|E| \log |V|)$ that find the second shortest path between $s∈V$ and $t∈V$. The farthest I managed to ...
Daniel's user avatar
  • 71
2 votes
0 answers
63 views

Borůvka's step in linear time

I am trying to understand this Expected linear time MST algorithm, and I have a problem in the implementation of the Borůvka's step. My problem is with the removal of duplicate edges between merged ...
Nathaniel's user avatar
  • 15.7k
1 vote
0 answers
51 views

Complexity of topological sorting with a special restriction

Let $G = (V, E)$ be a connected DAG (representing a circuit) with every vertex may be one of the following three types: Input variable, with in-degree $0$ and out-degree $\geqslant 1$. A gate, with ...
user779130's user avatar
-2 votes
2 answers
209 views

Could this novel algorithm be qualified to be published in Nature or Science

I recently designed an algorithm for single-source shortest paths in graph structures, which can limit the number of edges as Bellman-Ford while approaching the performance of SPFA. Of course, it also ...
Shawxing Kwok's user avatar
1 vote
0 answers
21 views

O(n^3) Algorithm for Maximum Weighted Cycle Cover for Undirected Complete Graph with Triangle Inequality

I have been trying to implement an approximation algorithm for the max traveling salesman problem with triangle inequality, and each paper I've read references the step of finding the max cycle cover ...
ConfusedGerbil's user avatar
1 vote
2 answers
115 views

NP-hardness of modified distance-colouring of graphs

Given a graph $G =(V,E)$, a set of colors $\mathcal{C}=\{0,1,2,3,...,c-1\}$, and an integer $r$, I want to know if I can find a coloring procedure that can assign a color to each nodes (all nodes must ...
r236's user avatar
  • 11
0 votes
1 answer
34 views

Fully Connected Graph to Lattice

I am looking for algorithms (or at least something similar to the problem definition): Given a fully-connected weighted graph $G$ with $n$ nodes, find a subset $S$ of edges that form a square lattice ...
EnderNicky's user avatar
1 vote
1 answer
31 views

Independent sets generation in a graph

Is there an algorithm that, given an undirected graph and one independent set IS1, finds an other independent set IS2 by adding and deleting vertices from the first IS1?
maliya's user avatar
  • 11
1 vote
1 answer
32 views

Algorithm for constructing a numbering reflecting the order of activities

I'm following a book about graphs and they introduce a concept called 'activity network'. In an activity network, each vertex represents an activity in a project (like building a house for example) ...
BMBM's user avatar
  • 231
2 votes
2 answers
35 views

Algorithm question - check if there exists a path that touches A nodes exactly once and can revisit all other nodes

I am having trouble with a problem where I am given an adjacency list and a list of the nodes that must be visited exactly once to connect two nodes. What is the most efficient way of doing this? This ...
Maceo Cardinale Kwik's user avatar
1 vote
1 answer
29 views

Graph Algorithms (SSSP vs MST)

I am currently facing a question "Can a graph with a unique MST product a different spanning graph using Dijkstra vs using Prim's algorithm?" The answer is false and I am struggling to ...
pehperclip's user avatar
1 vote
1 answer
84 views

Can Dijkstra's algorithm be used this way?

Let us say that I wanted to solve a Hamiltonian path problem by treating it as a Hamiltonian cycle(on a weighted graph). I use a TSP solver, and implement a dummy node of edge weight zero, whose ...
Johnny Upman's user avatar
1 vote
0 answers
19 views

epsilon-optimality in cycle-cancelling for min cost flow

I'm learning about the (min-mean) cycle-cancelling alg for min-cost flow in Ahuja, Magnanti, and Orlan's Network Flows book (Chapters 9 and 10). When talking about the alg, they prove this fact ...
AWhite's user avatar
  • 21
0 votes
1 answer
64 views

How to modify Dijkstra's algorithm to model the path of an electric car?

I know that Dijkstra's algorithm is used to find the shortest path between nodes in a weighted graph. And I know that this can be used to model road networks. Somebody online asked (but nobody ...
Johnny Upman's user avatar
0 votes
1 answer
134 views

Why not n^2 comparisons in the Alien Dictionary problem on leetcode?

Here's the problem statement (as given on GeeksForGeeks website): Given a sorted dictionary of an alien language having N words and k starting alphabets of standard dictionary, find the order of ...
Anurag Prasad's user avatar
2 votes
2 answers
161 views

A $O(|E||V|)$ algorithm to determine if a graph is singly connected?

In exercise 22.3-13 of CLRS (Intro to Algorithms 3rd edition), the authors provide the following problem: A directed graph $G = (V, E)$ is singly connected if the existence of a path from $u$ to $v$ ...
Hugh Mann's user avatar
0 votes
0 answers
23 views

Edge connectivity using flow network

Find an algorithm for edge connectivity in undirected graph using flow networks. Try to use $O(m)$ edges. So basically the flow network should be used as a "helper function" and the graph ...
popcorn's user avatar
  • 183
0 votes
1 answer
65 views

Optimizing Delivery Routes in a Graph-Based Network to Minimize Maximum Delivery Time

In a graph with N nodes, where each node represents a house and is labeled from 0 to N-1, an ...
maplemaple's user avatar
1 vote
1 answer
105 views

Expected maximum matching size in a random bipartite graphs

What is the expected maximum matching size of a bipartite graph $(A\cup B, V)$ where $\lvert A\rvert = n$ and $\lvert B\rvert = n$ and the probability of a edge existing between $A$ and $B$ is a fixed ...
Anonymous's user avatar
2 votes
1 answer
80 views

Dinitz’ algorithm in simple unit-capacity networks

I am studying for an algorithm design course, and can't understand this demonstration about how Dinitz’ algorithm computes a maximum flow in $O(m \sqrt{n})$ time. This is what is written on the slides ...
Placido Pellegriti's user avatar
0 votes
1 answer
39 views

Can a trie or DAWG loop?

I am looking at DAWGs, which are compressed tries, like this: It is an acyclic graph though, and I'm wondering if you are allowed to create loops or cycles in such a data structure. For example, I am ...
Lance's user avatar
  • 2,243
0 votes
0 answers
70 views

In Johnson's algorithm for enumerating elementary circuits in a directed graph, why do B-lists have a different structure than the adjacency list?

I have a question on the implementation of the Johnson's algorithm in C that is actually at the interface of theory and practice. Link to Johnson's paper I already implemented this algorithm in R ...
Olivier7121's user avatar
3 votes
1 answer
37 views

Increasing families of expander graphs

I would like to know if there is any research dealing with the problem of constructing an increasing family of expander graphs. The goal is to find a family of expander graphs $(G_i)_{i \in \mathbb{N}}...
sooolal's user avatar
  • 31
0 votes
0 answers
72 views

Lookup Using Path Matrix in Floyd Warshall Algorithm

How is the path matrix created by the Floyd Warshall algorithm used for path lookup? The 2 images show the graph (b) and the path matrix (c). Both are taken from the book: Foundations of Algorithms by ...
Labeeb Basil's user avatar
1 vote
1 answer
82 views

Number of decycling sets in a 3-regular planar graph

Defintitions: A graph is said to be r-regular if every of its vertex has a degree $r$. A graph is planar if it can be drawn in a plane without any of its edges intersecting each other except at their ...
Yolov4's user avatar
  • 73
8 votes
2 answers
1k views

Algorithmic Complexity of Recognizing Claw-Free Graphs

Let $H=\left(V_H, E_H\right)$ and $G=(V, E)$ be graphs. A subgraph isomorphism from $H$ to $G$ is a function $f: V_H \rightarrow V$ such that if $(u, v) \in E_H$, then $(f(u), f(v)) \in E$. $f$ is an ...
licheng's user avatar
  • 405
1 vote
1 answer
28 views

Linked Lists, Ordered Pairs?

I would like to model linked lists using set theory similar to that in Scheme and LISP. There is a set theoretic definition of the ordered pair: $p = \{\{a, 1\}, \{b, 2\}\}$ My question is how does ...
notaorb's user avatar
  • 111
1 vote
1 answer
19 views

How to avoid global delaunay check in conforming triangulation?

I implemented a conforming (i.e. it creates Steiner points using Ruppert's algorithm) delaunay triangulator, which is working, but there is one step I am doing that I straight up don't understand and ...
Makogan's user avatar
  • 341
3 votes
1 answer
56 views

Fast way to know if deleting an edge will disconnect a fully connected undirected graph

Given a fully connected undirected graph, is there a quick way for me to know if the graph will remain fully connected if I delete a given edge from the graph? Quick = O(lg V) or something like that. ...
morpheus's user avatar
  • 209
1 vote
1 answer
54 views

GNI public coin interactive proof: why randomize y?

I've read this scribe that provides a public coin interactive proof for graph non-isomorphism. In the proof, the verifier samples both a pairwise-independent hash function and a target $y$. Then it ...
AmirD's user avatar
  • 13
1 vote
0 answers
31 views

How to actually implement ruppert's algorithm?

I have been scouting the internet for resource son how to properly implement Ruppert's algorithm and what I ahve found is always lacking in details. The best resources I have so far are these 2: ...
Makogan's user avatar
  • 341

1 2
3
4 5
99