Informally, an algorithm is a set of explicit instructions used to solve a problem (e.g. Euclid's algorithm for computing the greatest common divisor of two integers). For more specific questions on algorithms, this tag may be used in conjunction with the approximation-algorithms, algorithmic-...

learn more… | top users | synonyms

0
votes
0answers
25 views

Relaxed path decomposition of a graph

Definition Given a directed connected graph $G$ without multiple edges or self loops. We call a final path of $G$ a path ending with a vertex with no successor (the path can not be extended anymore) ...
3
votes
1answer
77 views

Generating Uniquely k-Optimal Point Sets

This question is motivated by the observation that finding an optimal tour through a set of points in the Euclidean plane is especially simple, if the points are in convex configuration and, that the ...
10
votes
7answers
1k views

Where on the internet I can find database of graphs?

I am studying graph algorithms. I need database of graphs on which I can test my algorithms. Where can I find reliable database of graphs of all kinds? Thanks!
0
votes
0answers
82 views

Finding good high-dimensional sphere coverings in Euclidean space

Suppose we want to cover the unit sphere $\mathcal{S}^{d-1} := \{\mathbf{x} \in \mathbb{R}^d: \|\mathbf{x}\|_2 = 1\}$ with spherical caps $\mathcal{C}_{\mathbf{y}} := \{\mathbf{x} \in \mathcal{S}^{d-1}...
0
votes
1answer
255 views

Efficient isomorphic subgraph matching with similarity scores

I'm a computer vision PhD student, and I'm looking for an efficient approximation to the following problem, which could end up helping in image to image matching. Failing that, pointers to relevant ...
6
votes
1answer
203 views

Algorithm for Low Discrepancy Sequence of Hamilton Cycles in Complete Graphs

Are there deterministic algorithms that generate a sequence of Hamilton Tours that is superior to a sequence of randomly chosen tours, when applied to the TSP (by applying to the TSP, I understand ...
0
votes
0answers
32 views

Minimizing component-wise convex functions [migrated]

I want to minimize a function $f(\vec x,\vec y)$, whereby $\vec x$ and $\vec y$ are vectors. If I hold $\vec x$ constant, $f(\vec x,\vec y)$ is convex with respect to $\vec y$, and the reverse is true ...
3
votes
2answers
794 views

Find all faces in a graph from list of edges

I have the information from a undirected graph stored in a 2D array. The array stores all of the edges between nodes, e.g. graph[3] might be equal to [1,8,30] and represents the fact that node 3 ...
0
votes
0answers
37 views

How to find faces of graph? [duplicate]

I have à planair graph and I want to find an algorithm that will find all of the faces of the graph. Thanks you in advance for your answers.
5
votes
0answers
93 views

“Factorisation” in special linear groups over rings of integers

It is known that for any number field $F$ with infinitely many units (i.e. $F$ is not $\mathbb Q$ or an imaginary quadratic field) with ring of integers $O$ the special linear group $\mathrm{SL}_2(O)$ ...
-2
votes
1answer
104 views

Algorithm for finding numbers with an even partition number

NOTE: After edit question became about set partitions, which not was I intended, so this is second try. Is there an algorithm for producing an infinite subset of set of integer partition numbers p(n) ...
8
votes
1answer
738 views

Doob Martingale: Where is the catch?

I am working on a research problem in uncertainty propagation that involves sums of possibly dependent random variables with bounded sets of support. I am attempting to use the method of bounded ...
1
vote
2answers
60 views

How can I efficiently approximate the stationary distribution of an infinite CTMC with a sparse rate matrix?

I am looking for methods to approximate the stationary distribution of an infinite CTMC with a sparse rate matrix. Each row and column of the rate matrix has a finite number of non-zero elements. ...
4
votes
0answers
85 views

In what range can we find diophantine approximations using the LLL-algorithm?

Let $\alpha_1, \ldots, \alpha_n$ be $\mathbb{Q}$-linearly independent real numbers. I want to show that for all $x_1, \ldots, x_n\in\mathbb{Z}$, $|x_i|<N$ we have some lower bound for $\left|\sum ...
3
votes
0answers
42 views

Connectedness of semi algebraic set by c.a.d

I do not know whether there is a standard or some traditional ways to decide whether a semi algebraic set is connected or not. One way I know is c.a.d algorithm. I have read some papers of c.a.d ...
0
votes
0answers
19 views

Counting contingency tables with unary inputs

Given $2$ sequences $A = (a_1,\dots,a_k)$ and $B = (b_1,\dots,b_l)$ of natural numbers. A contingency table is a matrix in $\mathbb{N}^{k \times l}$ with row sums $A$ and column sums $B$. Counting ...
4
votes
0answers
149 views

Optimal instructions for the modular construction of rectlinear Lego structures

Let $X$ be a compact (or periodic) union of integer translates of unit cubes such that the interior of $X$ is connected. (If it makes any difference, suppose that the dimension $n$ of $X$ is 3.) I am ...
4
votes
2answers
5k views

Reporting all faces in a planar graph

Hi, I was looking to traverse a planar graph and report all the faces in the graph (vertices in either clockwise or counterclockwise order). I have build a random planar graph generator that creates a ...
5
votes
0answers
154 views

Solving polynomial equations modulo $1$

Let $P\in \mathbb{R}\lbrack x\rbrack$ be given. (In practice, the coefficients could be given as, say, decimals to sufficient precision.) Let $M\geq 1$, and let $I$ be an interval in $\mathbb{R}/\...
0
votes
0answers
43 views

Reconstructing a graph from set of sequences of edges

I have the following problem to solve: Given a set of sequences of edges of an undirected, planar, connected graph, find a "reasonable" reconstruction of the graph. There is an unknown number of ...
1
vote
1answer
57 views

Is there analogs of perlin noise algorithm?

I want to create procedure generated map, but all resources that I found talks about using of "perlin noise" algorithm. Maybe better (higher perfomance, more realistic terrain generation) analogs ...
9
votes
0answers
95 views

Factorisation in $\mathbb{N}[X]$?

Do we know an efficient algorithm to factorise in $\mathbb{N}[X]$ ? One way to do factorisation in $\mathbb{N}[X]$ is to use an algorithm to factorise in $\mathbb{Z}[X]$ and to combine some factor to ...
6
votes
2answers
817 views

What is the Time Complexity of the Matrix Exponential?

While trying to compute the Matrix Exponential of an $n \times n$ array I decided to take advantage of a Python function called scipy.linalg.expm(). According to ...
2
votes
0answers
158 views

Complexity of an algorithm to solve linear diophantine equations

A friend of mine ask me yesterday a problem, however, the interesting part for me it is not his problem, but what I will ask here. I want to know the optimal complexity of an algorithm (I mean the ...
0
votes
3answers
101 views

How to do a clockwise ordering of a planar graph in order to define its faces?

I am currently making an algorithm for planar graphs that I need to triangulate so they become maximally planar (that is triangulated and planar) given only the lists of neighbors for each node : no ...
4
votes
1answer
640 views

Covering the integers by two kinds of three-element sets (IMO Shortlist 2001 problem C4): extensions and generalizations?

As a straightforward generalization of IMO Shortlist 2001 problem C4, we can show the following fact: Let $u$ and $v$ be two positive integers. A set of three integers $\left\lbrace x,y,z\right\...
0
votes
0answers
16 views

Finding orthogonal basis with constraint

Is there any fast algorithm that output an orthogonal basis $e_i,i\leq n$ of $R^n$ with $e_i\in V_i$? Where $V_i,i\leq n$ are given linear subspaces of $R^n$. And is there any condition on $V_i,i\leq ...
19
votes
3answers
1k views

A generalization of the triangle counting problem for simple weighted graphs

One nice identity is that $$\operatorname{tr}(A^3)/6$$ counts the number of triangles of a graph with adjacency matrix $A$. It also implies that triangle counting in a graph can be performed in sub-...
2
votes
2answers
300 views

Irreducible algebraic sets via irreducible polynomials

There are many results about irreducible polynomials over finite fields: we know a cardinality of all irreducible polynomials with given degree, we know explicit examples of irreducible polynomials, ...
7
votes
3answers
299 views

A simplified Art Gallery Problem in a matrix

Let's take a $m \times n$ matrix as an area with $m \times n$ blocks (likes a 2D-version of the world in Minecraft). We have to put some lamps in this matrix to illuminate the whole matrix. Here is ...
7
votes
1answer
285 views

Choosing two-colorable subgraph in a triangulation

Consider a planar graph $G$ which is a triangulation. Is it possible to find a two-colorable subgraph $H$ of $G$ which has a common edge with every face of $G$? It is known that it is not always ...
0
votes
2answers
88 views

Shortest path in a weighted graph with coloured edges

I have a weighted undirected graph with $N$ veritces and $M$ edges with 10 different colours in the whole graph. Each time I pass edges of different colour I have to pay additional fee equal to $K$. ...
8
votes
1answer
288 views

How long does the slow inefficient algorithm for computing the product in classical Laver tables take?

Let $(A_{n},*)$ denote the $n$-th classical Laver table. Let $X_{n}$ be the set of all finite sequences of elements from $A_{n}$. Define a function $E_{n}:X_{n}\rightarrow X_{n}$ by letting $E_{n}((...
28
votes
9answers
12k views

Fast Matrix Multiplication

Suppose we have two $n$ by $n$ matrices over particular ring. We want to multiply them as fast as possible. According to wikipedia there is an algorithm of Coppersmith and Winograd that can do it in $...
14
votes
4answers
1k views

Checking if two graphs have the same universal cover

It's possible I just haven't thought hard enough about this, but I've been working at it off and on for a day or two and getting nowhere. You can define a notion of "covering graph" in graph theory, ...
4
votes
1answer
295 views

an algebraic variety for a boolean circuit

There is a polynomial reduction from a $3-CNF$ $SAT$ problem to some system of polynomial equations over $\mathbb{F}_2$. I mean there is polynomial reduction $F$ such that for every boolean ...
3
votes
0answers
371 views

Finding the number of rational points effectively

Consider $\# P$ and $\oplus P$. There is a $\# P$-hard problem: to find number of rational solutions of a system of polynomial equations over $\mathbb{F}_2$. The corresponding $\oplus P$-hard ...
1
vote
0answers
79 views

maximal sets of vertices that avoids a clique

I am looking for some known algorithm that finds, for a given graph, all the maximal sets of vertices that avoid a clique of some given size $k$. I'd prefer one written in MATLAB, but other languages ...
7
votes
1answer
94 views

Fast Fourier Transforms for non-trigonometric bases

The fast Fourier transform allows decomposition into a sin/cos basis in $N \log(N)$ complexity. Can one generalize the algorithm (or the ideas used) to other bases, e.g. orthogonal polynomial bases ...
4
votes
0answers
54 views

Efficient CW structures on squarefree semi-algebraic set

General Setup Given a collection of $k$ polynomials (with real coefficients) in $n$ real variables, say $f_i(x_1,\ldots,x_n)$, let $V \subset \mathbb{R}^n$ correspond to those $x$-values for which ...
1
vote
2answers
51 views

Practical permutation search problems resilient to backtrack techniques

I asked a similar question here: Permutation search problems with no known $o(n!)$ algorithms; to which one-way functions over a space of permutations gives a problem with no $o(n!)$ solution (...
3
votes
1answer
89 views

A modified bipartite assignment problem

Consider the following optimization problem. I have $n$ advisors and $dn$ students. I want to assign each student an advisor so that each advisor has exactly $d$ students. Each advisor/student pair ...
1
vote
2answers
112 views

The cost function in the Weighted Bipartite Matching Problem (a.k.a the Assignment Problem)

In the definition of this problem, the weight/cost function generally takes value in $\mathbb{Z}$ (or sometimes $\mathbb{Q}$). This is what I observed from some books (e.g. "Combinatorial ...
2
votes
0answers
39 views

smallest ball enclosing one point of each color

I have a set of colored points (say 10 colors with 50 points of each color) in a 100-dimensional space. I want to choose one point of each color so that the 10 points are as close to each other as ...
12
votes
2answers
208 views

Permutation search problems with no known $o(n!)$ algorithms

I am looking for problems for whose solution no known subfactorial algorithms are known. I am particularly interested in questions of isomorphism; that is, is there a permutation that converts one ...
0
votes
0answers
33 views

Comparing product of positive affine functions over integers

Problem Let $f_i: \mathbb Z^n \mapsto \mathbb Z$ and $g_i: \mathbb Z^n \mapsto \mathbb Z$ affine functions and $\mathcal D \subseteq \mathbb Z^n$ a set on which they are all positive. Let $P$ and $Q$ ...
1
vote
2answers
401 views

Terrain Generation: Infinite 2D space filled with Diffusion-limited aggregation clusters?

Disclaimer: I don't have a deep understanding of fractals or any higher math, I'm just personally interested in it, so please excuse me if I'm using wrong terms or if I'm being inaccurate. Making ...
3
votes
0answers
86 views

State of the art for univariate complex polynomials factorization with algebraic coefficients

Let $\mathbb{K}:=\overline{\mathbb{Q}}$ be the field of algebraic numbers. We choose to represent an element of $\mathbb{K}$ as its minimal monic polynomial, which is a vector in some $\mathbb{Q}^n$. ...
3
votes
2answers
101 views

Algorithms for Sorting Subset Sums

In this question the number of unique sortings has been discussed. As a follow-up, I would like to know, whether the problem of sorting the sequence of subset sums has ever been studied. There ...