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 ...
• 1,015
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 ...
• 454
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: \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{...
• 153
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 ...
• 23
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 ...
• 557
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 ...
• 131
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 ...
• 194
1 vote
29 views

1 vote
45 views

• 4,631