Skip to content
Free planNo credit card requiredStart writing
AI for Research home
AI for Research home
Dashboard
Sign inGet started

Search 250 million research papers

Read the abstract, see who wrote it and who cites it, and get the citation in APA, MLA, Chicago or Harvard.

About 2,714 papers for “tree embedding”

Embedding of and + into Arbitrary Tree

Vijender Kumar, Anil Kumar · 2013

We present an approach to find the edge congestion sum and dilation sum forembedding of square of cycle on n vertices, Cn 2 , and Cn 2 −1 + K1 into arbitrary tree. The embedding algorithms use a technique based on consecutive label property. Our algorithm calculates edge congestion in linear time.

Cited by 0

Embedding Tree-Related Graphs Into Hypercubes

Sook-yeon Kim, Kyung-yong Chwa · 2007

We propose a general strategy of many-to-one embedding of treerelated graphs into hypercubes. These tree-related graphs include complete binary tree (CBT), mesh of trees (MOT), pyramid and so on. This strategy evenly distributes the same level nodes of a tree-related graph to the nodes of a hypercube. This distribution is a great advantage because the same level nodes are always activated simultaneously in most algorithms of tree-related structure. Using this strategy, we design several embedding methods that are more cost effective than those in previous work. These methods provide minimal or near minimal values in the embedding measures, such as dilation, load factor and congestion. Concerning CBTs, we design two methods: one with the minimal dilation and the other with the minimal load factor. The congestion of both methods is minimal. In addition, we also show that both the dilation and load factor cannot be simultaneously minimized when the same level nodes of the CBT are evenly ...

Cited by 0

Decision Tree Embedding by Leaf-Means

Cencheng Shen, Yuexiao Dong, Carey E. Priebe · ArXiv.org · 2025

Decision trees and random forest remain highly competitive for classification on medium-sized, standard datasets due to their robustness, minimal preprocessing requirements, and interpretability. However, a single tree suffers from high estimation variance, while large ensembles reduce this variance at the cost of substantial computational overhead and diminished interpretability. In this paper, we propose Decision Tree Embedding (DTE), a fast and effective method that leverages the leaf partitions of a trained classification tree to construct an interpretable feature representation. By using the sample means within each leaf region as anchor points, DTE maps inputs into an embedding space defined by the tree's partition structure, effectively circumventing the high variance inherent in decision-tree splitting rules. We further introduce an ensemble extension based on additional bootstrap trees, and pair the resulting embedding with linear discriminant analysis for classification. We establish several population-level theoretical properties of DTE, including its preservation of conditional density under mild conditions and a characterization of the resulting classification error. Empirical studies on synthetic and real datasets demonstrate that DTE strikes a strong balance between accuracy and computational efficiency, outperforming or matching random forest and shallow neural networks while requiring only a fraction of their training time in most cases. Overall, the proposed DTE method can be viewed either as a scalable decision tree classifier that improves upon standard split rules, or as a neural network model whose weights are learned from tree-derived anchor points, achieving an intriguing integration of both paradigms.

Cited by 0Open access

Isotree: Tree clustering via metric embedding

Bai Xiao A, Andrea Torsello B, Edwin R. Hancock C et al. · 2008

This article appeared in a journal published by Elsevier. The attached copy is furnished to the author for internal non-commercial research and education use, including for instruction at the authors institution and sharing with colleagues. Other uses, including reproduction and distribution, or selling or licensing copies, or posting to personal, institutional or third party websites are prohibited. In most cases authors are permitted to post their version of the article (e.g. in Word or Tex form) to their personal website or institutional repository. Authors requiring further information regarding Elsevier’s archiving and manuscript policies are encouraged to visit:

Cited by 0

Embedding of Tree Machines into Hypercubes

2008

In this paper, we present that a tree machine can be embedded into incomplete hypercube with expansion 1, load 1, dilation 2 and congestion 2. This result is better than the expansion (2 h+1 +2 h)/(2 h+1 +2 h-2) in [14]. Then we consider how to embed a large tree machine into a hypercube for considering load-balance. We have shown that a tree machine TMh (h�1) can be embedded into a hypercube Hh+1 with dilation 1, congestion 2 and load 2, and a tree machine TMh can be embedded into Hn (h�n�1) with dilaton 1, congestion 3 and load 2 h-n+1 +2 h-n. The load of these embeddings is well balanced. 1

Cited by 0

Approximating Directed Steiner Problems via Tree Embedding

Rothvoß, Thomas · arXiv (Cornell University) · 2011

Directed Steiner problems are fundamental problems in Combinatorial Optimization and Theoretical Computer Science. An important problem in this genre is the k-edge connected directed Steiner tree (k-DST) problem. In this problem, we are given a directed graph G on n vertices with edge-costs, a root vertex r, a set of h terminals T and an integer k. The goal is to find a min-cost subgraph H subseteq G that connects r to each terminal t in T by k edge-disjoint r, t-paths. This problem includes as special cases the well-known directed Steiner tree (DST) problem (the case k=1) and the group Steiner tree (GST) problem. Despite having been studied and mentioned many times in literature, e.g., by Feldman et al. [SODA'09, JCSS'12], by Cheriyan et al. [SODA'12, TALG'14], by Laekhanukit [SODA'14] and in a survey by Kortsarz and Nutov [Handbook of Approximation Algorithms and Metaheuristics], there was no known non-trivial approximation algorithm for k-DST for k >= 2 even in a special case that an input graph is directed acyclic and has a constant number of layers. If an input graph is not acyclic, the complexity status of k-DST is not known even for a very strict special case that k=2 and h=2. In this paper, we make a progress toward developing a non-trivial approximation algorithm for k-DST. We present an O(D*k^{D-1}*log(n))-approximation algorithm for k-DST on directed acyclic graphs (DAGs) with D layers, which can be extended to a special case of k-DST on "general graphs" when an instance has a D-shallow optimal solution, i.e., there exist k edge-disjoint r, t-paths, each of length at most D, for every terminal t in T. For the case k=1 (DST), our algorithm yields an approximation ratio of O(D*log(h)), thus implying an O(log^3(h))-approximation algorithm for DST that runs in quasi-polynomial-time (due to the height-reduction of Zelikovsky [Algorithmica'97]). Our algorithm is based on an LP-formulation that allows us to embed a solution to a tree-instance of GST, which does not preserve connectivity. We show, however, that one can randomly extract a solution of k-DST from the tree-instance of GST. Our algorithm is almost tight when k and D are constants since the case that k=1 and D=3 is NP-hard to approximate to within a factor of O(log(h)), and our algorithm archives the same approximation ratio for this special case. We also remark that the k^{1/4-epsilon}-hardness instance of k-DST is a DAG with 6 layers, and our algorithm gives O(k^5*log(n))-approximation for this special case. Consequently, as our algorithm works for general graphs, we obtain an O(D*k^{D-1}*log(n))-approximation algorithm for a D-shallow instance of the k edge-connected directed Steiner subgraph problem, where we wish to connect every pair of terminals by k edgedisjoint paths.

Cited by 33Open access

Embedding planar graphs using PQ‐tree algorithms

Norishige Chiba, Takao Nishizeki, Shigenobu Abe et al. · Electronics and Communications in Japan (Part I Communications) · 1984

Abstract The problems of testing the planarity of a graph and of embedding a planar graph in a plane arise in many applications. This paper presents a simple linear algorithm for the latter problem. the algorithm is based on the “vertex‐addition algorithm” of Lempel, Even and Cederbaum for planarity testing and is a slight modification of Booth and Lueker's implementation of the testing algorithm using a PQ‐tree. Compared with the embedding algorithm known as the “path‐addition” algorithm of Hopcroft and Tarjan, our algorithm is conceptually simple and easy to understand or implement.

Cited by 5

Embedding tree structures in massively parallel computers

Jaafar Gaber, Bernard Toursel, Gilles Gonçalves et al. · 1995

Trees are an important class of computational structures due to their favoumble property of logarithmic path from the root to any leaf element. Since simple and regular interconnections among nodes are needed, they are easily manipulated.

Cited by 3Open access

Tight Bounds for On-line Tree Embedding

Bhatt, Sandeep, Greenberg, David, Leighton, Tom et al. · CaltechAUTHORS (California Institute of Technology) · 1991

Many tree–structured computations are inherently parallel.
\nAs leaf processes are recursively spawned they can
\nbe assigned to independent processors in a multicomputer
\nnetwork. To maintain load balance, an on–line
\nmapping algorithm must distribute processes equitably
\namong processors. Additionally, the algorithm itself
\nmust be distributed in nature, and process allocation
\nmust be completed via message–passing with minimal
\ncommunication overhead.
\n
\nThis paper investigates bounds on the performance
\nof deterministic and randomized algorithms for on–line
\ntree embedding. In particular, we study tradeoffs between
\nperformance (load–balance) and communication
\noverhead (message congest ion). We give a simple technique
\nto derive lower bounds on the congestion that
\nany on–line allocation algorithm must incur in order to
\nguarantee load balance. This technique works for both
\nrandomized and deterministic algorithms, although we
\nfind that the performance of randomized on-line algorithms
\nto be somewhat better than that of deterministic
\nalgorithms. Optimal bounds are achieved for several
\nnetworks including multi–dimensional grids and butterflies.

Cited by 0Open access

Embedding tree computations into the RAW chip

Adrian Mihail Soviani · DSpace@MIT (Massachusetts Institute of Technology) · 2002

The main goal of this thesis is to provide coarse grain parallelism for the RAW chip. Coarse grain parallelism can be expressed by using instrumented function calls which are queued and executed on other processors. Function calls are reassigned to adjacent processors only. Subsequently, a computation tree is dynamically embedded into the processor mesh (Chapter 3). A C library interface was developed to provide this mechanism: applications can spawn function calls, and wait at synchronization points (Chapter 4). Two imple-mentations of the spawn interface were built as part of the thesis project: i) a system that runs on the RAW chip using interrupting messages to implement work scheduling and synchronization (Chapter 5); ii) a generic spawn library based on POSIX threads that uses shared memory and locking (Chapter 6). Embedding computation trees into 2D processor meshes proved to be successful for a selection of tree structures and mesh sizes. Two models were used for testing: a perfect binary tree, and a Fibonacci tree.

Cited by 0Open access

Hierarchical Correlation Clustering and Tree Preserving Embedding

Morteza Haghir Chehreghani, Mostafa Haghir Chehreghani · 2024

We propose a hierarchical correlation clustering method that extends the well-known correlation clustering to produce hierarchical clusters applicable to both positive and negative pairwise dissimilarities. Then, in the following, we study unsupervised representation learning with such hier-archical correlation clustering. For this purpose, we first investigate embedding the respective hierarchy to be used for tree preserving embedding and feature extraction. Thereafter, we study the extension of minimax distance measures to correlation clustering, as another representation learning paradigm. Finally, we demonstrate the performance of our methods on several datasets.

Cited by 4

Embedding Tree Structures in VLSI Hexagonal Arrays

Dan Gordon, Israel Koren, Gabriel M. Silberman · IEEE Transactions on Computers · 1984

Tree structures have been proposed for special-purpose and general-purpose multiprocessors due to their desirable property of logarithmic path from the root to any leaf element. Since only local communication among processors is needed in tree structures, they are well suited for the VLSI technology. Such an implementation requires an area-economical mapping of a tree on a plane. Novel mapping schemes for trees onto hexagonal arrays (or grids) and appropriate algorithms are proposed here and shown to be superior over known mappings on square arrays (or grids).

Cited by 37