# Tag Info

Accepted

### Improving Bloom filter - can we distinguish elements of a database using less than 2.33275 bits/element?

2.09 bits per element is practically achievable. See http://cmph.sourceforge.net/: "[Compress, Hash, Displace] can generate MPHFs that can be stored in approximately 2.07 bits per key." 1.44 bits per ...
• 11.2k
Accepted

### How fast can we find and disconnect roots in a forest?

The problem has name "fringe marked ancestor problem" and indeed has $O(\log \log n)$ worst-case solution for both operations [1], thus overcoming the lower bound for generic version of the problem. ...
Accepted

### Complexity of reachability in directed rooted forests

The problem is L-complete. It’s easier to think about it when the edges are written backwards. That is, I will consider the problem formulated as follows: given a directed acyclic graph such that ...
• 18.2k
Accepted

• 1,318
Accepted

### Spanning Tree that Preserves the Number of Branch Vertices

No, not even close. Lemma 1. For any $n\ge 6$, all $n$ vertices in the complete bipartite graph $K_{3,n-3}$ are branch vertices, but each spanning tree of the graph has at most 4 branch vertices. ...
• 10.9k

### O(n)-space, polylog-time subtree sums in incremental forests?

Thanks to Dmytro Taranovsky for the thorough answer. Here's my attempt to rephrase his answer in my own words. Without loss of generality, assume that $G$ consists of a single tree. First, we reduce ...
• 393

### Is there a regular tree language in which the average height of a tree of size $n$ is neither $\Theta(n)$ nor $\Theta(\sqrt{n})$?

I believe that the answer is as you suggest that no other asymptotics than $\Theta(1)$, $\Theta(\sqrt{n})$ and $\Theta(n)$ are possible. A promising route to prove this could be to apply the ...

### Algorithm for computing unordered tree edit distance

A student of ours recently looked into a dynamic programming A* algorithm for computing the unordered tree edit distance (although we adapted it for the ordered tree edit distance). I was not directly ...
• 21

### Place of tree-adjoining grammars in the hierarchy of tree grammars

Actually I've found the answer. Here is quote from unpublished work (lecture notes?) of M. Kanazawa: The class of tree languages of tree-adjoining grammars is included in the class of tree ...

### What are "unranked trees"?

You are Right if the Computing Power for XSD schema is free or freely available (Soft). Otherwise, it will be Hard.
Accepted

### What are some techniques for "balancing" a tree beside heavy-light and centroid decomposition?

The paper "Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth" (Elberfeld, Jacobi, Tantau) gives a nice balanced tree decomposition based on tree contraction in $TC^0$: ...
• 500
1 vote
Accepted

Based on the comment of Michael Wehar, I've found this grammar to be that one which doesn't have an equivalent MCFTG: $S\rightarrow T(a,a)$ $T(x_1,x_2)\rightarrow T(b(x_1,x_2),c(x_1,x_2))$ $T(x_1,... 1 vote ### How to continue this algorithm? A conceptually far simpler algorithm is to try all the options. Cut the rectangle into$g=gcd(w,\ell)$squares. There are finitely many ways to portion these squares into non-overlapping blocks that ... • 1,046 1 vote Accepted ### Regarding proper form of production rules of Context-free tree grammars After a couple of hours of thinking I found at least proper form of grammar. Thanks to @Sylvain's commentary and link to Fisher's paper, which given me a clue. Proper context-free tree grammar, which ... 1 vote ### Finding a minimum tree which is isomorphic to a subtree of$T_1$but not to a subtree of$T_2$Your problem is in$P$. In fact, it can be solved in$O(n^2)$time. Given a tree, you can find a label (a binary string) that is a canonical form for the tree (i.e., all isomorphic trees will share ... • 12.3k 1 vote Accepted ### A non-trivial combinatorial optimization This is NP-hard even for$d=1$by reduction from the (strongly NP-hard) Product Partition problem. Lemma 1. The problem (with either objective function) is NP-hard, even for$d=1\$. Proof sketch. Given ...
• 10.9k

Only top scored, non community-wiki answers of a minimum length are eligible