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 8,021 papers for “Tree decomposition”

Tree-Decomposition

Joshi, Archit Pradeep, N R, Aravind · Research Archive of Indian Institute of Technology Hyderabad (Indian Institute of Technology Hyderabad) · 2017

The focus of this thesis is the concept of tree-decomposition. A tree-decomposition of a graph G is a
\nrepresentation of G in a tree-like structure. Sometimes problems which are NP-hard in general are
\nsolvable in polynomial or even linear time when restricted to trees. Many problems can be solved
\ne

Cited by 0

Tree-Structured Shading Decomposition

Geng Chen, Hong-Xing Yu, Sharon Zhang et al. · 2023

We study inferring a tree-structured representation from a single image for object shading. Prior work typically uses the parametric or measured representation to model shading, which is neither interpretable nor easily editable. We propose using the shade tree representation, which combines basic shading nodes and compositing methods to factorize object surface shading. The shade tree representation enables novice users who are unfamiliar with the physical shading process to edit object shading in an efficient and intuitive manner. A main challenge in inferring the shade tree is that the inference problem involves both the discrete tree structure and the continuous parameters of the tree nodes. We propose a hybrid approach to address this issue. We introduce an auto-regressive inference model to generate a rough estimation of the tree structure and node parameters, and then we fine-tune the inferred shade tree through an optimization algorithm. We show experiments on synthetic images, captured reflectance, real images, and non-realistic vector drawings, allowing downstream applications such as material editing, vectorized shading, and relighting. Project website: https://chen-geng.com/inv-shade-trees.

Cited by 2

The pipeline decomposition tree:

Dong-Ik Ko, Shuvra S. Bhattacharyya · 2006

Modern embedded systems for image processing involve increasingly complex levels of functionality under real-time and resource-related constraints. As this complexity increases, the application of single-chip multiprocessor technology is attractive. To address the challenges of mapping image processing applications onto embedded multiprocessor platforms, this paper presents a novel data structure called the pipeline decomposition tree (PDT), and an associated scheduling framework, which we refer to as PDT scheduling. PDT scheduling exploits both heterogeneous data parallelism and task-level parallelism, which are important considerations for scheduling image processing applications. This paper develops the PDT representation for system synthesis, and presents methods using the PDT to derive customized pipelined architectures that are streamlined for the given implementation constraints.

Cited by 6

Distributed tree decomposition with privacy

Vincent Armant, Laurent Simon · SPIRE - Sciences Po Institutional REpository · 2012

Tree Decomposition of Graphical Models is a well known method for mapping a graph into a tree, that is commonly used to speed up solving many problems. However, in a distributed case, one may have to respect the privacy rules (a subset of variables may have to be kept secret in a peer), and the initial network architecture (no link can be dynamically added). In this context, we propose a new distributed method, based on token passing and local elections, that shows performances (in the jointree quality) close to the state of the art Bucket Elimination in a centralized case (i.e. when used without these two restrictions). Until now, the state of the art in a distributed context was using a Depth-First traversal with a clever heuristic. It is outperformed by our method on two families of problems sharing the small-world property.

Cited by 0Open access

Decomposition of k-Dense Tree

L. FLORES PACHECO, G. FRANCESCHINI, F. LUCCIO et al. · CINECA IRIS Institutial research information system (University of Pisa) · 2001

Cited by 0

Geometric Decomposition of Spider Tree

E Ebin, Raja Merly, D. Subitha et al. · International Journal of Science and Research (IJSR) · 2016

2 3n and a r . Clearly q = . If a = 1 and r = 2 then q = 2 n -1. In this paper we study the Geometric Decomposition of spider tree.

Cited by 0Open access

Tree Decomposition of Multiclass Problems

Ana Carolina Lorena, André C. P. L. F. de Carvalho · 2008

Several popular machine learning techniques are originally designed for the solution of two-class problems. However, several classification problems have more than two classes. One approach to deal with multiclass problems using binary classifiers is to decompose the multiclass problem into multiple binary subproblems disposed in a binary tree. This approach requires a binary partition of the classes for each node of the tree, which defines the tree structure. This paper presents two algorithms to determine the tree structure taking into account information collected from the used dataset. This approach allows the tree structure to be determined automatically for any multiclass dataset.

Cited by 3

Tree decomposition: A feasibility study

Von Hein Röhrig, Angefertigt Thema, Herrn Prof et al. · 1998

Graphs of small treewidth resemble a tree in a certain (precise) sense. Many computationally hard graph problems can be solved efficiently on graphs of small treewidth using a “tree decomposition, ” which represents the constructive aspect of treewidth. However, computing minimum-width tree decompositions is NP-hard in general, but for fixed treewidth, there exist algorithms with polynomial running time. In order to evaluate the practical usability of tree-decomposition algorithms for graphs of arbitrary treewidth, we have implemented several fundamental algorithms related to computing tree decompositions. We present the theory behind solving graph problems using tree decompositions and show how it can be applied in practice to compute “path decompositions.” Then we give a survey of the tree-decomposition algorithms considered and discuss their practical value on the basis of benchmarks. Test graphs were produced using a suite of graph-generating programs

Cited by 0

Grammar Factorization by Tree Decomposition

Daniel Gildea · Computational Linguistics · 2011

We describe the application of the graph-theoretic property known as treewidth to the problem of finding efficient parsing algorithms. This method, similar to the junction tree algorithm used in graphical models for machine learning, allows automatic discovery of efficient algorithms such as the O(n 4 ) algorithm for bilexical grammars of Eisner and Satta. We examine the complexity of applying this method to parsing algorithms for general Linear Context-Free Rewriting Systems. We show that any polynomial-time algorithm for this problem would imply an improved approximation algorithm for the well-studied treewidth problem on general graphs.

Cited by 20Open access

Graph generation using tree decomposition

Shirzad, Hamed · Summit (Simon Fraser University) · 2021

We propose TD-GEN, a graph generation framework based on tree decomposition, and introduce a reduced upper bound on the maximum number of decisions needed for graph generation. The framework includes a permutation invariant tree generation model which forms the backbone of graph generation. Tree nodes are supernodes, each representing a cluster of nodes in the graph. Graph nodes and edges are incrementally generated inside the clusters by traversing the tree supernodes, respecting the structure of the tree decomposition, and following node sharing decisions between the clusters. Finally, we discuss the shortcomings of standard evaluation criteria based on statistical properties of the generated graphs as performance measures. We propose to compare the performance of models based on likelihood. Empirical results on a variety of standard graph generation datasets demonstrate the superior performance of our method.

Cited by 0Open access