Hot answers tagged

20 votes

How can I find the second cheapest spanning tree?

The second-smallest spanning tree differs from the minimum spanning tree by a single edge swap. That is, to get the second-smallest tree, you need to add one edge that's not already in the minimum ...
user avatar
9 votes
Accepted

Exact formula for the number of spanning trees of a rectangle

According to https://www.cse.ust.hk/~golin/pubs/ANALCO_05.pdf there is no closed-form formula known. According to http://arxiv.org/pdf/cond-mat/0004341v1.pdf the number is asymptotic (for $n$ and $m$ ...
user avatar
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 ...
user avatar
  • 11k
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. ...
user avatar
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 ...
user avatar
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 $...
user avatar
  • 3,381
5 votes
Accepted

How does Camerini's algorithm for minimum-bottleneck-spanning-tree run in linear time?

First, after each stage throw away any isolated vertices. With these vertices removed (even when the graph is disconnected) the number of vertices in the next stage will be at most twice the number of ...
user avatar
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....
user avatar
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$ ...
user avatar
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 ...
user avatar
  • 11k
4 votes

How can I find the second cheapest spanning tree?

Could not add a comment due to lack of reputation. As commented by David Eppstein you can find the proof of the fact that the second-smallest spanning tree differs from the minimum spanning tree by a ...
user avatar
  • 141
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 ...
user avatar
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 ...
user avatar
3 votes
Accepted

Graph (Forest) representation that supports edge deletion and efficient traversal

This problem is known as Decremental Connectivity. In general, decremental connectivity is where you need to support the operations: Connected($u$,$v$) : Check whether vertex $u$ is connected to ...
user avatar
  • 423
3 votes

Pre order traversal of an array

I think the best way is to make a recursive algorithm. You could divide your input in half (approx), and keep out the central element. Then you recursively build a tree with the left subarray which ...
user avatar
  • 168
3 votes

Efficient algorithms for searching a collection of trees

Although not specifically aimed at (rooted) trees, I think the G-trie data structure might perform quite well in your setting. It is an adapation of the trie (for searching sets of strings) to graphs.
user avatar
3 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 ...
user avatar
  • 13.2k
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 ...
user avatar
  • 814
2 votes

Pre order traversal of an array

Although this is not exactly the question you asked, you can also build balanced trees from ordered data in an online manner. That is to say, you could walk your array from left-to-right building up ...
user avatar
  • 31
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 ...
user avatar
  • 181
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 ...
user avatar
2 votes

What is a zipper, and how does it relate to a tree-like structure?

A zipper is in general a pair of things: it's a structure-with-a-hole, a focus, representing where in the structure you are, together with a path, recording how you got to that focus. (This path is ...
user avatar
2 votes
Accepted

Alternating tree automata for arbitrary arity tree

An alternating tree automaton for arbitrary degree trees has a transition function of the following type: $$\delta:Q\times \Sigma\times D\to {\cal B}(\mathbb{N}\times Q)$$ where ${\cal B}$ is the set ...
user avatar
  • 5,261
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.
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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$: ...
user avatar
  • 490
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 ...
user avatar
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}$. ...
user avatar
  • 211
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 ...
user avatar

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