Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userExperimental Comparison of PC-Trees and PQ-Trees
111
0
0.0
(
0
)
Added by
Simon D. Fink
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
PQ-trees and PC-trees are data structures that represent sets of linear and circular orders, respectively, subject to constraints that specific subsets of elements have to be consecutive. While equivalent to each other, PC-trees are conceptually much simpler than PQ-trees; updating a PC-trees so that a set of elements becomes consecutive requires only a single operation, whereas PQ-trees use an update procedure that is described in terms of nine transformation templates that have to be recursively matched and applied. Despite these theoretical advantages, to date no practical PC-tree implementation is available. This might be due to the original description by Hsu and McConnell in some places only sketching the details of the implementation. In this paper, we describe two alternative implementations of PC-trees. For the first one, we follow the approach by Hsu and McConnell, filling in the necessary details and also proposing improvements on the original algorithm. For the second one, we use a different technique for efficiently representing the tree using a Union-Find data structure. In an extensive experimental evaluation we compare our implementations to a variety of other implementations of PQ-trees that are available on the web as part of academic and other software libraries. Our results show that both PC-tree implementations beat their closest fully correct competitor, the PQ-tree implementation from the OGDF library, by a factor of 2 to 4, showing that PC-trees are not only conceptually simpler but also fast in practice. Moreover, we find the Union-Find-based implementation, while having a slightly worse asymptotic runtime, to be twice as fast as the one based on the description by Hsu and McConnell.
rate research
Read More
We consider the design of adaptive data structures for searching elements of a tree-structured space. We use a natural generalization of the rotation-based online binary search tree model in which the underlying search space is the set of vertices of a tree. This model is based on a simple structure for decomposing graphs, previously known under several names including elimination trees, vertex rankings, and tubings. The model is equivalent to the classical binary search tree model exactly when the underlying tree is a path. We describe an online $O(log log n)$-competitive search tree data structure in this model, matching the best known competitive ratio of binary search trees. Our method is inspired by Tango trees, an online binary search tree algorithm, but critically needs several new notions including one which we call Steiner-closed search trees, which may be of independent interest. Moreover our technique is based on a novel use of two levels of decomposition, first from search space to a set of Steiner-closed trees, and secondly from these trees into paths.
We consider a natural variant of the well-known Feedback Vertex Set problem, namely the problem of deleting a small subset of vertices or edges to a full binary tree. This version of the problem is motivated by real-world scenarios that are best modeled by full binary trees. We establish that bo
We give a new algorithm to construct optimal alphabetic ternary trees, where every internal node has at most three children. This algorithm generalizes the classic Hu-Tucker algorithm, though the overall computational complexity has yet to be determined.
In the classical Steiner tree problem, given an undirected, connected graph $G=(V,E)$ with non-negative edge costs and a set of emph{terminals} $Tsubseteq V$, the objective is to find a minimum-cost tree $E subseteq E$ that spans the terminals. The problem is APX-hard; the best known approximation algorithm has a ratio of $rho = ln(4)+varepsilon < 1.39$. In this paper, we study a natural generalization, the emph{multi-level Steiner tree} (MLST) problem: given a nested sequence of terminals $T_{ell} subset dots subset T_1 subseteq V$, compute nested trees $E_{ell}subseteq dots subseteq E_1subseteq E$ that span the corresponding terminal sets with minimum total cost. The MLST problem and variants thereof have been studied under various names including Multi-level Network Design, Quality-of-Service Multicast tree, Grade-of-Service Steiner tree, and Multi-Tier tree. Several approximation results are known. We first present two simple $O(ell)$-approximation heuristics. Based on these, we introduce a rudimentary composite algorithm that generalizes the above heuristics, and determine its approximation ratio by solving a linear program. We then present a method that guarantees the same approximation ratio using at most $2ell$ Steiner tree computations. We compare these heuristics experimentally on various instances of up to 500 vertices using three different network generation models. We also present various integer linear programming (ILP) formulations for the MLST problem, and compare their running times on these instances. To our knowledge, the composite algorithm achieves the best approximation ratio for up to $ell=100$ levels, which is sufficient for most applications such as network visualization or designing multi-level infrastructure.
We study sublinear and local computation algorithms for decision trees, focusing on testing and reconstruction. Our first result is a tester that runs in $mathrm{poly}(log s, 1/varepsilon)cdot nlog n$ time, makes $mathrm{poly}(log s,1/varepsilon)cdot log n$ queries to an unknown function $f$, and: $circ$ Accepts if $f$ is $varepsilon$-close to a size-$s$ decision tree; $circ$ Rejects if $f$ is $Omega(varepsilon)$-far from decision trees of size $s^{tilde{O}((log s)^2/varepsilon^2)}$. Existing testers distinguish size-$s$ decision trees from those that are $varepsilon$-far from from size-$s$ decision trees in $mathrm{poly}(s^s,1/varepsilon)cdot n$ time with $tilde{O}(s/varepsilon)$ queries. We therefore solve an incomparable problem, but achieve doubly-exponential-in-$s$ and exponential-in-$s$ improvements in time and query complexities respectively. We obtain our tester by designing a reconstruction algorithm for decision trees: given query access to a function $f$ that is close to a small decision tree, this algorithm provides fast query access to a small decision tree that is close to $f$. By known relationships, our results yield reconstruction algorithms for numerous other boolean function properties -- Fourier degree, randomized and quantum query complexities, certificate complexity, sensitivity, etc. -- which in turn yield new testers for these properties. Finally, we give a hardness result for testing whether an unknown function is $varepsilon$-close-to or $Omega(varepsilon)$-far-from size-$s$ decision trees. We show that an efficient algorithm for this task would yield an efficient algorithm for properly learning decision trees, a central open problem of learning theory. It has long been known that proper learning algorithms for any class $mathcal{H}$ yield property testers for $mathcal{H}$; this provides an example of a converse.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
