Peter Taylor
  • Member for 11 years
  • Last seen more than 1 year ago
  • Spain
Formalizing and optimizing constraints involving booleans, pairs of booleans, and integer sums
1 votes

It's certainly possible to simplify the presentation: A graph $G = (V, E)$ A weight function $w_1 : V \mapsto \mathbb{N}$ A weight function $w_2 : E \mapsto (\mathbb{N} \cup \{-\infty\})$. This ...

View answer
Enumerate all allocations of points in a simplex
0 votes

From the set of $2^m$ possible allocations, only $m+1$ allocations can be attained by the above procedure. Why? The boundary between the two halves of the allocation is the line $w_xx = w_yy$; the ...

View answer
Deciding whether a graph contains a complete balanced bipartite graph
Accepted answer
5 votes

If the vertex pair $(u, v)$ is not in $E$ then they can't be on opposite sides of the partition, so they must be in the same half. Create a union-find data structure and merge every vertex pair which ...

View answer
How can algorithms with nested combinatorial searches be quasi-linear?
2 votes

As I see it, that is a combinatorial problem, i.e. exhausting which number and composition of vertices constitutes a suitable set. No, it's just a selection problem, for which there are well-known ...

View answer
Practical/heuristic algorithm for multi set-cover
2 votes

You'd have to tweak the limits (in particular max_level may be too low), but for at least some "real" problems this is within the bounds of Knuth's algorithm M. See also The documentation of ...

View answer
Constructing integer sets in which a certain equation has no solution
0 votes

This has been studied in the case of the specific linear equation $$x + y = w + z$$ where (allowing trivial solutions such as $x=w, y=z$) the set $S$ is a Golomb ruler / Sidon set. In this case, the ...

View answer
For which graphs is the DFS tree always a path?
Accepted answer
13 votes

This is equivalent to the property that you can construct a Hamiltonian path by greedily taking an arbitrary edge at every vertex. Searching for greedy Hamiltonian path turned up: Greedily ...

View answer
How hard is recognizing a permutation that is a square for the shift product?
Accepted answer
4 votes

It's really quite easy. Let $$\rho_k = \left( \begin{matrix}1&2&\ldots&n\\ (k+1)\bmod n&(k+2)\bmod n&\ldots&(k+n)\bmod n\end{matrix} \right)$$ be the shift permutation. Then ...

View answer
Enumerating set combinations in an order that maximises the number of previously unseen subsets
Accepted answer
1 votes

There are $\sum_{j=1}^4 \binom{11}{j} = 561$ smaller subsets, and each $x^\phi$ contains $\sum_{j=1}^4 \binom{5}{j} = 30$ of them. If you put all $462$ $5$-element sets in a priority queue with ...

View answer
What is the most efficient way to generate a random permutation from probabilistic pairwise swaps?
15 votes

This isn't a full answer by any means, but it includes a result which may be useful and applies it to get some constraints on the case $n=4$ which limit the possible 5-gate solutions to 2500 easily ...

View answer
Was Babbage's Analytical Engine really turing-complete?
Accepted answer
4 votes

Your question states: However, the instruction set as devised by Babbage seems to support only going back or jumping ahead one single punched card. However, the link you supply as a reference for ...

View answer
Help on the following combinatorial problem?
Accepted answer
8 votes

I've rethought this and my initial bound was correct. In the worst case, $|S| = \Theta(m \; 2^\frac{m}{\lg m})$ Proof is in two parts. Firstly, $|S| = O(m \; 2^\frac{m}{\lg m})$. Consider the ...

View answer
Finding all cycles
1 votes

You can avoid the multiple passes over the same elements by using a union set data-structure. One pass over each element $s$ unioning the set containing $s$ with the set containing $f(s)$. This still ...

View answer
Route existence between n pairs of nodes
0 votes

Topological sort ($O(m+n)$) then work down it propagating a bitset of nodes from which each node can be reached ($O(m n)$). After the topological sort you can do a $O(n)$ quick-rejection (if node $n+...

View answer
Covering a set of intervals
Accepted answer
6 votes

You're right to look for a reduction from the subset-sum problem. The subset problem is to find a subset $S'$ of $S$ such that $\Sigma_{s' \in S'} s' = t$. But this can be reduced to ...

View answer
A special class of languages: “circular” languages. Is it known?
6 votes

@Dave Clarke, L = a*|b* would be circular, but L* would be (a|b)*. In terms of decidability, a language $L$ is circular if there is an $L'$ such that $L$ is the closure under + of $L'$ or if ...

View answer
Is any related work to this m-trails problem ?
2 votes

What is $f$? I seems that you're asking for a one-to-one mapping between a power set over a power set of edges and the edges - which would surely be possible only if there's no more than one edge.

View answer
Finding twin vertices in graphs
5 votes

Because of the crazy system on this site I can't comment directly, but I have a couple of observations on existing answers. I'm pretty sure Hsien-Chih Chang's solution needs to correct $A^2$ to $AA^T$...

View answer
Binary multiplication and parity convolution
2 votes

Sure, you can reduce it to a factor of 1, but probably at the cost of time. But to answer the question behind the question: multiplication of polynomials mod 2 is easier from a hardware point of view (...

View answer