# Questions tagged [algorithms]

An algorithm is a sequence of well-defined steps that defines an abstract solution to a problem. Use this tag when your issue is related to design and analysis of algorithms.

1,976 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
56 views

### Max nodes whose value exceeds all neighbors

A node is valid if its value is greater than all of its incident edges. Task is to maximize the number of valid nodes. Given $n$ values for nodes and $n-1$ values for edges, how do I assign these ...
14 views

### Algorithm for animating/morphing convex polygon diagrams

I am trying to find an algorithm to smoothly morph a (given) diagram made of convex polygons into another (given) diagram of the same type. The target diagram is usually generated from the source, ...
52 views

35 views

### Gin heuristic algorithm design

(Apologies if this or an equivalent question has been asked in the past; I didn't see anything that answered this question.) I'm designing an algorithm to compute a heuristic for a Gin game engine. (...
127 views

### Help understanding how to make a simple 3D minimum bounding sphere?

I need to develop a minimum bounding sphere. It'll only ever be in 3 dimensions, and the numbers of points are relatively small (500-5000 total). Performance is important however. I was looking for ...
54 views

### Modifying the JPEG compression to use custom block patterns

recently, while watching a video about machine learning, I had an idea about creating an image compression algorithm, that works similar to JPEG, but is based on arbitrary bitmaps as blocks. I should ...
163 views

99 views

### Split a graph into 2 components with known distribution?

I'm trying to find a method to randomly split a connected planar graph $G$ into two connected components, such that the sum of the weights of vertices in each component are relatively close. (If there ...
81 views

### Polynomial time algorithms for rank 1 elliptic curves over Q

As an outsider, it sounds like a lot of progress has been made on understanding rank 1 elliptic curves. Much of the BSD conjecture is known for rank 1, and Heegner points provide a way to calculate a ...
236 views

### How to select a loop nesting trees for irreducible loops?

I am trying to understand the process of analyzing a control flow graph and building a tree of loops, both reducible (single entrypoint) and irreducible (multiple entrypoint), using the algorithm ...
302 views

131 views

### Edmond's Blossom algorithm (Maximum Matching) explanation

I asked this question on Math Stackexchange but it didn't get much attention, so I am asking it here. Edmond's Blossom algorithm (Wikipedia), or simply the blossom algorithm, is a popular graph ...
161 views

### Is the Bakery Lock fair?

Consider this implementation of the Bakery Lock: ...
548 views

I want to write a scheduling algorithm for the following scenario: There is a set of tasks to complete, each one with a due date, difficulty (easy, normal, hard) and progress on the task. The idea is ...
72 views

### Optimal ordering of items with contradictory constraints

I've got a set of items that I'd like to sort into a list. The items have two independent sets of constraints that the ordering should respect: A set of hard constraints that must be satisfied, e.g.: ...
210 views

### Find all pairs of nodes whose deletion disconnects graph

Given undirected, connected graph, find all pairs of nodes (connected by an edge) whose deletion disconnects the graph. There can't be an edge connecting a node to itself. The problem seems similar ...
137 views

### How to find the top k pairwise product of in an array of integers?

Input: An array $a$ of integers $[a_{1}, \cdots, a_{n}]$, and a positive integer $k$. Output: The the top-k products of pairs in $a$. Example: $a = [7,6,5,4,3,2,1],k=3$ , output $(42,35,30)$, with ...
1k views

### Finding all possible paths in a directed, (possibly) cyclic graph

I need to find all possible paths in a directed graph, that may have loops. The graph has a defined start and one or multiple defined endings. Basically im trying to find all possible scenarios in a ...
116 views

### How to find a minimum spanning forest with a constrained number of nodes in each spanning tree?

Consider a weighted undirected acyclic graph consists of m source (root) vertices and n target vertices. The m-spanning tree problem of the graph is defined as that: (1) each of the m spanning trees ...
61 views

### Simon's algorithm in quantum computing

I am curios how simon's algorithm works and I have read this post Simple explanation of Simon's Problem but still is not clear for me. I have found on th internet this example https://www.cs.vu....
49 views

### Efficient approximation for find all the nodes and edges which match with some sub-tree in a graph

Let's suppose that I have a big digraph D and a small tree T (small w.r.t D), both directed, D can be connected or not, but T is connected. Here an example: Let's say that D is as follow: And T is ...
107 views

### Survival algorithm for Network deterministic failures

Consider an undirected network $G = (V,E)$ in which edge $e$ $\in$ $E$ fails after (deterministic) time $t(e) > 0$. Network failure occurs at the first instant in which $G$ is no longer connected. ...
108 views

### Is there an optimization problem on planar graphs which is APX-hard ?

I'm looking for a optimization problem on planar graphs which is APX-hard, which means that it doesn't admit a PTAS (approximation scheme). It would be even better is the difficulty of the problem ...
158 views

### How to minimize the sum of edge weight in the graph while keep the all-pair shortest path greater than a constant?

For example, if we have a graph G = (V, E) and a subset of vertices $U \subset V$. We can set $w(e)$ where $e \in E$ to be a non-negative real number. We want to minimize the total edge weight, but ...
95 views

### Are there are satisfying explanations for why genetic algorithms work?

The following commentator writes: Having studied this extensively back when they were called Genetic Algorithms, I would like to offer a few insights. One of the biggest reasons they fell out ...
What's the best/optimal known method/algorithm known that can be used to calculate the number of binary $M_{m,n}$ matrices for given $n,m$, whose $1$'s are all connected? Or equivalently, to ...