# Questions tagged [graphs]

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

4,838 questions
Filter by
Sorted by
Tagged with
1 vote
34 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 ...
11 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 its nodes. For example, I have tasks of types A, B, and C. A-type tasks are placed in all the leaf nodes of the dataflow ...
32 views

### Non-dominated maximal paths (DAG)

Let $D(V, A)$ be a DAG. We call a dominated path in $D$ a path $P$ such that $\quad\quad P$ is maximal and $\exists_{P^{'} \in D}(P^{'} \text{ is maximal } \wedge V(P) \subset V(P^{'}))$ that is, $P$ ...
25 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 ...
10 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 ...
22 views

### Mapping relationtional data to hierarchical data (JSON, XML, etc.)

I'm working on a project that involves mapping relational data to a tree hierarchy. The hierarchical data is preferred to be JSON or XML. Is there an existing general algorithm for this? Current ...
31 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 ...
42 views

### The second shortest path on a directed graph

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 get ...
1 vote
53 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 ...
40 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 ...
193 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 ...
13 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 ...
43 views

33 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 ...
1 vote
77 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 ...
48 views

### Reductions to perfect matching

Can we reduce any well-known problems to deciding whether a (possibly non-bipartite) graph $G$ has a perfect matching? I'm particularly interested in finding a reduction from deciding whether a ...
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 ...
1 vote
22 views

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 ...
1 vote
14 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 ...
44 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. ...
1 vote
47 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 ...
1 vote
26 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: ...
245 views

### An efficient way to find a pair of unrelated edges

I'm writing a program which uses an undirected graph to represent certain social connections, and I'm trying to check whether or not it's contains a specific induced subgraph. Given a dense an ...
28 views

### Why is there no self-stabilizing determinsitic algorithm for vertex coloring in general graphs?

This question considers the design of a deterministic self-stabilizing algorithm for vertex coloring in uniform anonymous networks. Uniform anonymous networks do not have distinguished nodes and all ...
1 vote
77 views

### Time complexity of using BFS to find shortest path within k stops

I'm referencing this Leetcode question: https://leetcode.com/problems/cheapest-flights-within-k-stops/solution/, which asks you to find the length of the shortest path from source to dest using less ...
31 views

### Probabilistic Pathfinding

Here an interesting graph problem I've recently saw: After a heist in New York City, a group must reach Miami within a set timeframe to catch an escape boat. Their vehicle's GPS shows U.S. routes with ...
11 views

### Constructing a sparse subgraph of original weighted undirected graph with approximation algorithm

In Kruskal's algorithm, we sort edges from least weight to greatest weight and add the edge if and only if both endpoints are in different connected components in current iteration. Now the question ...
27 views

### Is there a fully dynamic algorithm to find a minimum arborescence (like Chu–Liu/Edmonds' algorithm)?

Given a weighted directed graph with nonnegative edge weights and a vertex $r$ designated as root, at each step I will do one of the following: Add a new edge to the graph. Remove an edge from the ...
26 views

### A* (A-star) search algorithm including closest distance from a node to an obstacle in heuristic and step cost

I want to include the distance of a node to the closest obstacle in the cost function, so that the path length is not only minimal, but also not near obstacles. We know that: Dijkstra's algorithm uses ...
1 vote
Consider a graph tree $T$, where we are given $k > 1$ unique pairs of nodes $\{u_1,v_1\}\dots \{u_k,v_k\}$. Let $P_{i}$ denote the unique path on $T$ between $u_i$ and $v_i$. Then, my problem is ...