Questions tagged [algorithms]

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-randomness and algorithmic-topology tags.

Filter by
Sorted by
Tagged with
-2
votes
0answers
119 views

Showing primality of $1\bmod4$ integers

If $p$ is an integer that is $1\bmod 4$ and we know a representation of $p$ in the form $p=a^2+b^2$ then is there a deterministic polynomial time algorithm to conclude primality or not of $p$ without ...
2
votes
1answer
181 views

Solving multilinear equations

Let $N=\{1,2,\ldots,n\}$. Suppose we are given $n$ equations, with each equation taking the form $\sum_{A\subseteq N}\left(c_A \prod_{i\in A}x_i \right) = 0$, where each $c_A$ is a real number ...
1
vote
0answers
26 views

Finding minimum weight perfect matchings in sparse bipartite graphs

Question: What can be recommended for finding optimal perfect matchings in large bipartite graphs with small vertex degree if the edge-weights are positive real values? I am looking for ...
1
vote
1answer
109 views

Integrality certification for product of two matrices $A B^{-1}$

Let's consider two non-singular integer matrices $A,B \in\mathbb{Z}^{n\times n}$. I want a test to check if $A\times B^{-1}$ is integral (or no denominators). I am referring the unimodular ...
-2
votes
0answers
17 views

Search Algorithm in d-D Tucker

The algorithm of search a complementary edge in TUCKER seems to need at most O(n^2) time complexity. How to query with fewer vertices?
1
vote
1answer
72 views
+100

Max weighted matching where edge weight depends on the matching

Given a bipartite graph $G$, we seek a maximal weighted matching $E$. The particularity is below. Once an edge $e$ is chosen, the action of choosing $e$ adds a negative weight $w(e,e')$ to any other ...
0
votes
0answers
10 views

Finding weight minimal swap-free directed vertex covers

Suppose a complete directed graph is given with $n$ vertices and $n(n-1)$ weighted arcs $a_{ij}$ and we have $\omega(a_{ij}\ne\omega{a_{ji})$ for at least one pair of antiparallel arcs and the ...
3
votes
1answer
274 views

Arithmetic-geometric mean for rationals?

Let $\operatorname{AGM}(x,y)$ be the arithmetic-geometric mean of $x$ and $y$. Given an error $\varepsilon>0$, a bound $b\in\mathbb R_+$ and a function $f:\mathbb R\rightarrow\mathbb R$ with $f(x)=...
1
vote
2answers
86 views

For a given value of $n$ and $m$, find $\text{fib}(n)$ $\text{mod } m$ where $n$ is very huge. (Pisano Period) [closed]

Input Integers $'n'$ (up to $10^{14}$) and $'m'$(up to $10^3$) Output $\text{Fib}(n)$ $\text{modulo}$ $m$ My questions For example : Why $\text{fib}(n=2015)$ $\text{mod}$ $3$ is equivalent to $\...
0
votes
0answers
1k views

Shift and sort the sequence

Given a permutation of integers $1$ through $N$, we need to determine whether it is possible to sort this list in an increasing order by following certain conditions. The conditions imposed are : We ...
5
votes
3answers
115 views

Minimum number of swaps needed to 'group' a sequence?

Let a finite sequence $s=\{s_1,\dots,s_N\}$ (the characters of which are chosen from a finite set $\{c_1, \cdots, c_M\}$) be called "grouped" if for any $s_i=s_j$, $i<j$, we have $s_k=s_i=s_j$ for ...
0
votes
0answers
25 views

Enumerating all directed 3-cycle covers

It is fairly easy to enumerate the directed Hamilton cycles of a complete directed graph by fixing one of the vertices and enumerating the permutations of the others via one of the next-permutation ...
5
votes
1answer
96 views

Computational version of inverse sumset question

Let $p$ be prime and $\mathbb{F}_p$ the finite field with $p$ elements. Suppose we have a set $B\subseteq \mathbb{F}_p$ satisfying $|B|<p^{\alpha}$ for some $0<\alpha<1$ and there exists $A\...
4
votes
1answer
120 views

Enumerating antichains modulo permutation

I encountered the following combinatorics problem in my research, and I'd like to know if there is a reference or an easy solution for such a problem. Given a partially ordered set $\mathscr P$, an ...
1
vote
0answers
128 views

Algorithmic combinatorial discrete problem (randomized lazy update?)

We are given a vector $\mathbf{b}$ of size $h$. Initially we have $\mathbf{b}_i=1$ for all $i\in \{1, 2, \ldots, h\}$. In a sequential fashion, at each time step $t=1, \ldots, n$, an index $j(t)$ is (...
2
votes
0answers
42 views

Planarity of a subgraph

Given a complete symmetric graph $G(V,E)$ with real-valued edgeweights and assume that every induced $k_4$ that is induced by a quadruplet from $v$'s vertices has a unique perfect matching of maximal ...
1
vote
0answers
38 views

Formal definition of CBIP algorithm

I am working on online coloring algorithms and I felt on the implementation using the CBIP (Common boundary Intersection projection) method. However, there is not much documentation online about it. ...
0
votes
0answers
72 views

Ranking graph's nodes by score propagation

Problem I have the following directed tripartite graph $G(E\cup V\cup P, A)$, where there is a many-to-one symmetric relationship between the subsets V and E - $e\in E,v\in V,[e, v]\in A \iff [v, e]\...
0
votes
0answers
12 views

Statistics of trees in vertex-covering forests

What can be said about the properties of graphs $F$ that are generated from the edges of complete symmetric graphs $G(V,E)$ in the following way: fix an enumeration process for the edges in $E$ ...
8
votes
1answer
257 views

Transfinite algorithms

The Ford-Fulkerson algorithm is a classic algorithm that computes the maximum flow in a network. It is well-known that if irrational arc capacities are allowed, the algorithm does not necessarily ...
8
votes
0answers
181 views

Explicit construction of the Jacobian of a curve

Let $k$ be an algebraically closed field (of arbitrary characteristic), and $C$ a smooth projective curve over $k$, given by defining equations in projective space. I am looking for an algorithmic ...
1
vote
0answers
43 views

Graph coloring to minimize maximum number of colors along paths

Given a graph $G$ and a pair of source-destination nodes $s$ and $t$. Each node in $G$ is to be colored. Let $C_i$ denote the available color set for node $i$. Under a coloring scheme $A$, for any $s-...
0
votes
0answers
9 views

Sampling distribution on permutations with multi-dimensional constraints and nesting

Let $\mathcal{X}$ be some space (for argument's sake, a finite, discrete space of large cardinality), and let $D > 1$ be a positive integer. For $d = 1, \ldots, D$, Let $\Phi_d: \mathcal{X} \to ...
3
votes
0answers
69 views

Random sparse and invertible matrices

Let $n\leq m$ and $0\leq k\leq (n\times m - \min\{n,m\})$ be in $\mathbb{N}$. Let $\mu$ be a probability measure dominated by the Lebesgue measure on $\mathbb{R}$ and generate a random $n\times m$ ...
0
votes
0answers
22 views

Complexity of combined trajectory compression algorithm

Is it possible to calculate the complexity of the combined algorithms (TD-TR-SP, TD-SP-TR) provided here: A new perspective on trajectory compression techniques In more details, TD-TR-SP algorithm ...
0
votes
0answers
25 views

balls and boxes optimization

There are $n$ balls, among which $m$ balls are bad, and hence $n-m$ are good. We are given a number of boxes. We want to put balls into boxes such that all the good balls (or most of them, e.g., $99$%)...
1
vote
0answers
296 views

Finding elliptic curve with $P=[m]R$

To avoid X-Y problem I am going to write my problem down in detail, so plz bear with me. The elliptic curve over $Q$ given by a Weierstrass equation is - $E := y^2 +a_1 xy +a_3 y = x^3 + a_2 x^2+...
0
votes
0answers
78 views

Constructing set with maximal independent subset

What is the minimal $m$ such that there exists a set $A = \{a_1,...a_n\}$ of vectors : $a_i \in \{0,1\}^m$ ($n$ is given) such that every subset of vectors of size $k$ is independent, but only with ...
2
votes
1answer
52 views

Algorithms for heaviest edge-disjoint cycle collection contained in graph's set of edges

given a biconnected symmetric graph with weighted edges, what is the algorithmic complexity of determining a set of pairwise edge-disjoint cycles with maximal sum of edge weights if there are no other ...
0
votes
1answer
32 views

Starting point of roundtrip coloring in connected graphs

This is a subquestion for an older question about a certain kind of greedy coloring. Let $G = (V,E)$ be a finite, connected, simple, undirected graph. By a roundtrip of $G$ we mean a map $r:\{0,\...
3
votes
1answer
116 views

Given $n, c$ find $a>1,b$ such that $b ^ a \equiv c \pmod n$

Given a natural number $n$ (of unknown factorization) and an arbitrary number $c \in \mathbb{Z}^*_n$ (the set of natural numbers smaller than $n$ and coprime to it), is there an efficient algorithm ...
2
votes
0answers
46 views

3-uniform hypergraphs and their circuit space

So, I'll break this post into two questions. Both concern 3-uniform hypergraphs. A 3-uniform hypergraph $H=(V,E)$ consists of a set of vertices $V$ and a set of edges $E$, where each edge $e\in E$ is ...
0
votes
0answers
19 views

Calculating graph connectivity faster

this is a followup question to Identifying the edges that are essential for biconnectivity: consider a vertex-split graph $G(V,E)$ in which every vertex of a vertex-cut of size $k$ is adjacent to an ...
3
votes
1answer
104 views

summation of oscillating functions

Consider series of the form $S=\sum_{n\ge1}f(n)P(n)$, where $f$ is some smooth function, and $P$ is a periodic or quasi-periodic function (e.g., $P$ can be a trigonometric function, so $S$ a Fourier ...
1
vote
2answers
63 views

Identifying the edges that are essential for biconnectivity

Question: If $G(V,E)$ is a biconnected symmetric graph, is it possible to identify the edges, whose deletion destroys biconnectivity, in the following way: determine the union $B:= ST\cup F_1$ of ...
1
vote
1answer
78 views

Is Hamiltonian cycle fixed parameter tractable with parameter clique cover?

Let $G$ be connected simple graph. Clique cover of graph $G$ is partition of the vertices of $G$ into $k$ disjoint cliques $D'_i$. Given $G$ and $k$-clique cover, can we solve Hamiltonian cycle in ...
5
votes
3answers
480 views

Optimization algorithm sought

Suppose I have $N$ pairs of positive numbers $(a_1, b_1), (a_2, b_2), \dotsc, (a_N, b_N).$ and I want to find a subset of $M$ of them maximizing $$ \frac{\sum_{j=1}^M a_{i_j}}{\sum_{j=1}^M b_{i_j}}. $$...
1
vote
1answer
108 views

Finding a cycle of a specific length in an edge-weighted graph

I'm looking for some suggestions on how we might calculate cycles of a specific length in an edge-weighted graph. For example, imagine my phone tells me that I need to walk three miles today. It ...
2
votes
1answer
35 views

maximum weighted matching with weights being sets

Given a set $S$ and a bipartite graph $G$, each edge $v\in E(G)$ covers a subset $S_v$ of $S$. My problem is to find a matching maximizing the number of covered elements, i.e., denote $V$ the set of ...
1
vote
0answers
28 views

Computational complexity of higher order orthogonal iteration for Tucker decompositions

I am currently doing background reading for my Masters Thesis. I am working with tensor decompositions, where by tensor I simply mean a multi-dimensional array. The aim of my masters project is to ...
4
votes
2answers
145 views

Algorithm for reporting all triangles with unique interior point

What is known about the complexity of and/or practical algorithms for reporting all triplets of points from finite set of at least four points of which no three are collinear in the Euclidean plane, ...
8
votes
1answer
173 views

Freedom problem in hyperbolic groups

I will start with a general algorithmic question: Question. (A faithfulness decision problem.) Suppose that $G, H$ are finitely-presented groups with decidable word problem. Is injectivity decidable ...
0
votes
3answers
90 views

Calculating radii allowing for circular placement of polygonal linkage's joints

Given a planar polygonal linkage defined by a sequence of $n$ hinge joints $(j_0,\,\cdots,\,j_{n-1},j_n = j_0)$ with links of fixed lengths $\lbrace\|j_{k+1}-j_k\|=d_k\ |\ 0\le k\lt n\rbrace$ between ...
3
votes
1answer
227 views

Algorithm to generate free unlabelled trees uniformly at random

I am implementing an algorithm to generate free unlabelled trees uniformly at random (uar). For this I found this paper by Herbert S. Wilf (The uniform selection of trees. 1981. In Journal of ...
1
vote
1answer
90 views

Calculating the values of a generalization of binomials to permutations

let $$\Pi\binom{n}{k}:=\mathrm{card}\left( \left\lbrace \lbrace \Pi_1^n\,\cdots\,\Pi_k^n\rbrace\,|\,0\leq \pi_{r,c}\in\sum_{i=1}^k\Pi_i^n\ni\pi_{r,c}\leq 1\right\rbrace\right)$$ be the number of sets ...
2
votes
0answers
86 views

Time complexity of randomized algorithm: right-multiplying by random elements $z_i$ from a group $H$ to achieve $H$-invariance

Note: This question was inspired by a related question about the Quantum Merlin Arthur (QMA) complexity class on Quantum Computing Stack Exchange. I was deliberating whether to ask this on CS Theory ...
0
votes
1answer
72 views

a probability density algorithm that is not sensitive to the initial condition

There are many algorithms to estimate the density of probability distributions. I am looking for one that is not sensitive to the initial condition. For instance, Expectation–maximization algorithm ...
2
votes
0answers
70 views

Given positions find the symmetry group

Given a finite set of vectors in $\mathbb{R}^n$ ($n=2,3$), is there any algorithm to find its symmetry group? For example, if the input is {(1,0),(0,1),(-1,0),(0,-1)}, then the output is the dihedral ...
3
votes
0answers
66 views

Algorithm to compute minimal polynomials

Suppose $L/K$ is a finite Galois extension of fields of degree $n$. Suppose that we know an irreducible polynomial $f\in K[x]$ such that $L\cong K[x]/(f)$. Suppose also that we know the Galois group ...
-2
votes
1answer
70 views

Select one member from each set of set of numbers and to provide unique numbers in result set [closed]

I have set A of set B of set C of natural numbers (all finite), for example, ...

1
2 3 4 5
24