Hot answers tagged

24

In ArXiv:1002.4248, John Iacono and Özgür Özkan describe a relatively simple algorithm to merge two binary search trees in $O(\log^2 n)$ amortized time; the analysis is the hard part. [Update: As Joe correctly observes in his answer, this algorithm is due to Brown and Tarjan.] They also describe a more complicated dictionary data structure, based on biased ...


23

The cells in a $kD$-tree can have high aspect ratio, whereas octree cells are guaranteed to be cubical. Since this is a theory board, I'll give you the theoretical reason why high aspect ratio is a problem: it makes it impossible to use volume bounds to control the number of cells that you have to examine when solving approximate nearest neighbor queries. ...


18

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 spanning tree, and then remove the heaviest edge on the cycle that the added edge forms. If you already have the minimum spanning tree, this can all be done in ...


16

The following paper describes a slightly more efficient algorithm than Zhang-Shasha for computing tree edit distance, along with a proof that their algorithm is optimal (within a certain broad class of algorithms): Erik Demaine, Shay Mozes, Benjamin Rossman, and Oren Weimann. An Optimal Decomposition Algorithm for Tree Edit Distance. ACM Transactions on ...


14

The firefighter problem has received a fair amount of attention recently, and is (somewhat surprisingly) NP-hard on trees of maximum degree 3. It is actually a fairly natural question, described as follows: A fire breaks out at the root of the tree (or more generally, a specified vertex in a graph). At every step, the firefighter protects one non-burning ...


14

A zipper, in general, is a data structure with a hole in it. Zippers are used for traversing/manipulating data structures, and the hole corresponds to the current focus of the traversal. Typically there is also an element of the data structure under consideration, so that one has a (list) zipper and a list or a (tree) zipper and a tree. The zipper allows the ...


13

No, this is not new; range searching with multilevel B-trees is completely standard. See, for example, the following surveys: Lars Arge. External memory data structures. Handbook of Massive Data Sets (James Abello, Panos M. Pardalos, and Mauricio G. C. Resende, eds.), 313-357. Kluwer Academic Publishers, 2002. See especially sections 5 and 6. Jeffrey ...


12

It seems this is false in general. Take the tree with a central node $x$, connected to a bunch of nodes $y_1,\dots,y_n$. Each node $y_i$ is additionally connected to a node $z_i$. The total number of nodes is $N=2n+1$. Any caterpillar in this tree can contain at most two $z$ nodes, and therefore, $n/2$ caterpillars are needed to cover it. So it is ...


9

You may find this reference helpful: Brown and Tarjan, A Fast Merging Algorithm, in which the authors show how to merge balanced binary (AVL) trees in $O(n \log \frac{m}{n})$ which is optimal (for comparison based algorithms). $m$ and $n$ are the lengths of the sorted lists represented by the binary search trees, and it is assumed that $m \geq n$. You could ...


9

what are the advantages of octrees in spatial/temporal performance or otherwise, and in what situations are they most applicable (I've heard 3D graphics programming)? k-D trees are balanced binary trees and octrees are tries so the advantages and disadvantages are probably inherited from those more general data structures. Specifically: Rebalancing can be ...


9

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$ both large) to $$\exp (z_{\mathrm{sq}}mn)$$ where $$z_{\mathrm{sq}}=\frac{4}{\pi}\sum_{i=0}^\infty\frac{(-1)^i}{(2i+1)^2}\approx 1.16624$$ but I'm not sure ...


8

Empire colouring is NP-hard for trees. Let $r$ and $s$ be fixed positive integers, and let $G$ be a graph whose vertex set is partitioned into blocks (or empires) each containing exactly $r$ vertices. The $(s, r)$-colouring problem $s$-$\text{COL}_r$ asks for a colouring of the vertices of the graph $G$ that uses at most $s$ colours, never assigns the ...


8

Given a tree $T$, a partition of $V(T)$ in $k$ levels $\phi: V(T)\to \{1,\ldots, k\}$ (i.e., edges of $T$ connect vertices of neighbouring levels $i$ and $i+1$), and an integer $K$. Can you permute the vertices inside the levels such that the crossing number is at most $K$? This problem is NP-complete, proved by Martin Harrigan and Patrick Healy, $k$-Level ...


8

I would like to add to dkuper's answer that it is possible to split every tree into a hierarchy of caterpillars, whose depth is at most $O(\log n)$. This can be done with Tarjan's heavy-light edge decompostion. Just take the maximal heavy-edge paths as the spines of the caterpillars.


7

A useful survey on the topic, slightly out of date: Philip Bille. A survey on tree edit distance and related problems. Theoretical Computer Science, Volume 337, Issues 1–3, Pages 217–239, 2005. A recent paper on one of the versions of the problem: Tatsuya Akutsu et al. Exact algorithms for computing the tree edit distance between unordered trees. ...


7

A flow in a network is confluent if it uses at most one outgoing arc at each node. NP-hardness of determining a maximum confluent flow in a tree (of diameter 4, with multiple sinks allowed) is proved in: D. Dressler and M. Strehler, Capacitated Confluent Flows: Complexity and Algorithms, LNCS 6078 (2010) 347-358.


7

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 element is optimal. See "Hash, displace, and compress" "Improved Bounds For Covering Complete Uniform Hypergraphs" Data Structures and Algorithms , Vol. 1: ...


7

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. Their solution is based on Euler tour of the tree with union-split-find structure (and fast LCA for trees with unbounded degree). The same paper states that it ...


6

You can merge trees in $\bf\mathcal{O}(1)$ worst-case time whilst still supporting: insert, delete and search in $\mathcal{O}(log\ n)$. Unfortunately splitting causes problems, and would result in $\mathcal{O}(log\ n\ log\ log\ n)$ search and update times. Brodal, Gerth Stølting, Christos Makris, and Kostas Tsichlas. ‘Purely Functional Worst Case Constant ...


6

A harmonious coloring of a simple graph is a proper vertex coloring such that each pair of colors appears together on at most one edge. The Harmonious Chromatic Number of a graph is least number of colors in a harmonious coloring of the graph. This problem of finding Harmonious Chromatic Number was shown to be NP-complete on trees by Edwards and McDiarmid. ...


6

The Travelling Repairman Problem (TRP) is known to be NP-hard on weighted trees. In this problem, which is also sometimes called the Minimum Latency Problem, the goal is to find a tour that visits all the vertices of a graph while minimizing the average latency. The latency of a vertex $u$ is the cost of the tour from the origin until the tour visits $u$. ...


6

It depends a bit on what kind of problems you're looking at, but the path systems problem may be a candidate. Given: A finite set of propositions $P$, a set $A \subseteq P$ of axioms, a set $R \subseteq P \times P \times P$ of inference rules and some target $p \in P$. Question: Is $p$ provable from $A$ using $R$? Here, every proposition in $A$ is ...


6

[Steiner tree] remains NP-complete if all edge weights are equal, even if $G$ is a bipartite graph having no edges joining two vertices in $C$ or two vertices in $V-C$. — Garey and Johnson, Computers and Intractability, Freeman, 1979. Citation is to private communication with E. R. Berlekamp.


6

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 $t$. This problem is often known as "$k$ Most Vital Edges (for MST)", simply $k$-MVE (or sometimes $k$-MVE-MST to distinguish from other variations), as cited ...


5

Here is a counterexample, which I'm too lazy to draw. Let $G_1,G_2$ be diamonds, graphs on four vertices having five of the six edges. Connect matching vertices in $G_1$ and $G_2$ so that you get a connected cubic graph. It seems that there is no spanning tree in which every internal vertex has degree exactly $3$.


5

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 edges. Next, use the fact that (with isolated vertices removed, in each stage after the first) $|V|\le 2|E|$ to simplify the time bound in each stage (after ...


5

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. (In case we have to start with the empty tree, just insert $[n]$ in any order.) A result of Cleary [*1] (see also Lucas [*2]) shows that you can get from $...


4

First, Yixin Cao's comment that similarity is problem-specific is entirely correct. It doesn't make sense to talk about trees being similar or not, without having an idea of what you are trying to compute. That caveat aside, it is indeed very common to equip trees with metrics. One of the most common is to equip them with an ultrametric, where we define a ...


4

If you don't need deletions, I think the first part of Lemma 4.1 on page 349 of the following paper: Jeffery Westbrook: Fast Incremental Planarity Testing. ICALP 1992: 342-353 http://dx.doi.org/10.1007/3-540-55719-9_86 gives you a linear time algorithm for any sequence of operations consisting of constructing and marking the tree, as well as conducting ...


4

The problem is solved in the paper P. Slater. R-domination in graphs. J. ACM, 23(3):446–450, July 1976. It considers an even more general problem using dynamic programming.


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