# Questions tagged [ds.algorithms]

Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.

1,754 questions
Filter by
Sorted by
Tagged with
1 vote
53 views

### Efficient enumeration of connected functional digraphs (up to isomorphism)

Together with the research intern I am supervising, we are currently writing some software that requires us to enumerate all connected functional digraphs of $n$ vertices up to isomorphism (also known ...
130 views
+50

### Deciding if all matrix multiplication entries have at least two witnesses

Consider two square matrices $A(x,y)$ and $B(y,z)$ of dimensions $N×N$ containing boolean entries. Consider the output product matrix $C(x,z)$ where $C=AB$ (not boolean matrix multiplication but the ...
47 views

1 vote
139 views

### Nontrivial Algorithms for Coloring (Parameterized by Pathwidth)

Let $k$ be a positive integer. In the $k$-coloring problem, we are given a graph $G$ on $n$ nodes, and want to determine if there is a way to assign a color to each vertex of $G$ such that no two ...
38 views

### Reducing computing the partition function to computing the number of min-cardinality (s, t) cut

Consider a partition function for a graph as follows: \begin{equation} \mathrm{Z}_\mathrm{G}(\beta) = \sum_{z \in \{-1, 1\}^{n}} \beta^{\underset{(i, j) \in E, i < j}{\sum} w_{i,j} ~z_i z_j}, \end{...
150 views

### Another variation of $k$-means problem in the plane

According to wikipedia, consider $k$-means problem in the plane : k-means clustering aims to partition the $n$ observations into $k (≤ n)$ sets $S = \{S_1, S_2, \dots, S_k\}$ so as to minimize the ...
129 views

### Parameterized algorithm when the parameter is not known in advance?

In the setting of parameterized algorithms, we are typically given the problem instance as well as the value of the parameter. However, it seems like in applications the value of the parameter should ...
167 views

### Accessible entry for computational complexity theory through concrete problems

I am planning to start studying computational complexity theory. As the field is technical for a fresh undergrad alumni like me, I thought a good approach is to tackle it through areas I am more ...
98 views

### Optimal solution for partitioning convex polygon into small pieces

Given a convex polygon $P$ (possibly) with holes. We want to partition $P$ into a minimum number of connected interior-disjoint small pieces $Q_1,...Q_s$. The definition of small can either be that ...
67 views

### Interesting Variation on Subset Sum Problem

Does anyone have any ideas for this algorithms problem? Given an array $A$ with 40 integers ($-10^9 < A_i < 10^9$), how many ways are there to reach a target sum $X$. Normally, I would use ...
298 views

### A problem in understanding an algorithm

I read a paper from John Hershberger with this title: "Minimizing the sum of diameters efficiently". That paper proposed a simple algorithm that finds a bipartition of points $S$ in the ...
1 vote
29 views

1 vote
45 views