7
votes
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 ...
- 16.9k
7
votes
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
7
votes
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. ...
6
votes
Accepted
Complexity of "destroying" the graph's minimum spanning tree weight
EDIT
As noted in comments below, I originally read the question incorrectly. I thought the goal was to determine if removing $k$ edges could increase the MST weight of $G$ above some given threshold $...
- 3,382
5
votes
Notion of "quotient" or "inverse" for recognizable tree languages?
The Myhill-Nerode theorem characterizes regular/recognizable languages as those that have finitely many "quotients", and it works for trees — more precisely, a tree language is regular iff ...
5
votes
Accepted
For a given binary-search tree obtain an isomorphic splay tree
It can be done with a linear number of operations.
Suppose you start with an arbitrary given tree $T_0$ over keys $[n]$ and want to reach an arbitrary given $T$ over keys $[n]$ using splay operations....
- 1,306
4
votes
Minimum Spanning tree on a complete "random" graph
Let's consider a general model in which $L_n(\mu)$ is the (random) length of an MST on $K_n$, where the weight of each edge is sampled independently from a probability distribution $\mu$. When $\mu$ ...
- 18.1k
4
votes
Improving Bloom filter - can we distinguish elements of a database using less than 2.33275 bits/element?
1.56 bits per key is now possible using "RecSplit: Minimal Perfect Hashing via Recursive Splitting" by Emmanuel Esposito, Thomas Mueller Graf, and Sebastiano Vigna. It is quite expensive: 1,700 times ...
- 11.2k
4
votes
Accepted
O(n)-space, polylog-time subtree sums in incremental forests?
It turns out this is possible with $O(n \log n)$ preprocessing time, polylog ($O(\log^3 n)$) query time and linear space:
Convert the forest into binary trees of logarithmic height.
For each node, ...
- 2,537
4
votes
Accepted
If I naively generalize the homeomorphic embedding relation for labeled finite trees in this way, do I still have a wqo?
Here's a nice property of WQOs:
If $R$ is a WQO on terms, and $S$ is another transitive relation such that
$$ R\ \subseteq\ S$$
Then $S$ is a WQO
Proof: Let $t_1,\ldots, t_n,\ldots$ be an ...
- 13.7k
3
votes
Accepted
Reachability Query for Tree
Follow-up work by Holm, Rotenberg and Thorup [1] showed that there exists a reachability oracle for planar graphs of size $O(n)$ and query time $O(1)$. This is optimal also for trees (e.g., if the ...
- 839
3
votes
Accepted
Inexact labelled binary tree matching
I think that the problem is not hard, because if I understood the problem statement correctly, it can be solved in $O(|V|^2)$ time as follows:
We have two $0$-$1$-labeled rooted perfect full binary ...
3
votes
Accepted
How to constrain a finite automaton (NFA and DFA) to a tree?
I think the easiest way of enforcing tree shape is the set of conditions
$q_0$ is not in the image of $\delta$,
$\delta$ is injective, and
$M$ is connected (to avoid isolated cycles). Note that this ...
- 2,500
2
votes
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 ...
- 643
2
votes
NP-hard problems on trees
k-Balanced Partition Problem on graphs, in which one has to partition the $n$ vertices into $k$ connected components of size at most $\lceil\frac{n}{k}\rceil$ each and at the same time minimize the ...
- 181
2
votes
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
2
votes
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 ...
- 635
2
votes
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.
- 21
2
votes
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
2
votes
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.
...
- 9,595
2
votes
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
2
votes
Is the center of a BFS tree a good approximation of the graphs center?
In the worst case, this algorithm gives a 2-approximation (the trivial upper bound).
Take a cycle on some $n=4m$ vertices, vertex set $v_0,\ldots,v_{n-1}$, with one chord between $v_0$ and $v_{2m}$. ...
- 211
2
votes
Accepted
Binary Trees for Nearest Neighbor Search
This essentially can be derived from a compressed quadtree representing approximate Voronoi diagrams. If you want the decision tree to be balanced you have to use a finger tree on the compressed ...
- 9,596
2
votes
Accepted
Complexity of finding a path visiting all leaves on a tree while respecting a distance bound
As the comments have suggested, you are looking for a Ham Path through a set nodes in the $k$-leaf power graph of this tree. That is, given your tree $T$ and a distance $k$, form a graph $G$ where $V(...
- 1,276
1
vote
Accepted
Example of context-free tree language which can not be generated by monadic CFTG
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,...
- 635
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 ...
- 635
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 ...
- 11.7k
1
vote
Finding a minimum tree which is isomorphic to a subtree of $T_1$ but not to a subtree of $T_2$
You can put a tree into a cannonical form in $O(n)$ with leaf contractions. Read, Ronald C. (1972), "The coding of various kinds of unlabeled trees", Graph Theory and Computing, Academic Press, New ...
- 2,359
1
vote
How to constrain a finite automaton (NFA and DFA) to a tree?
Another idea, inspired by the pump lemma, would be to just say that there exists a maximum size N on words in the language, with N < |Q|. if there was a cycle, then you could repeat the cycle ...
- 26
Only top scored, non community-wiki answers of a minimum length are eligible