Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 12 of 12 for “"Tree-decompositions"”.
-
Connectivity, tree-decompositions and unavoidable-minors
… thesis introduces a refinement of the notion of tree-width. Tree-width is a measure of how “tree-like” a graph is. Essentially, a graph is tree-like if it can be decomposed across a collection of non-crossing vertex-separations into small pieces. In our variant, which we call k-tree-width, we …
-
Tree Graphs and Orthogonal Spanning Tree Decompositions
Given a graph G, we construct T(G), called the tree graph of G. The vertices of T(G) are the spanning trees of G, with edges between vertices when their respective spanning trees differ only by a single edge. In this paper we detail many new results concerning tree graphs, involving topics such as …
-
Computer representations of machined parts for automatic inspection
A comparison is made between octrees, which are regular decompositions of volumes, and new, irregular decompositions called R-trees. This comparison is made within the context of the volume intersection problems that might be associated with an automatic inspection system. The results show that the …
-
Solving Multiple Inference in Graphical Models
… by using an intelligent heuristic search on tree decompositions. The newest Min-Loss M-Best introduces a parameter-free method that directly minimizes the expected loss to simultaneously find the multiple top solution set.
-
Consequence-based reasoning for ontology classification
… framework with methods based on tree decompositions, and thus obtain what we believe are the first fixed-parameter tractability results for subsumption reasoning in DLs.</p>
-
Scalable Query Evaluation over Complex Probabilistic Databases
… inference algorithms, like Read-Once Formulas, Tree-Decompositions, Binary Decision Diagrams, Negation Normal Forms, when applied to the setting of probabilistic databases, which as we will see have their own distinct challenges and expectations, and (ii) building a robust system where the above …
-
Width functions for hypertree decompositions
Tree-width, a fundamental notion in graph structure theory, measures how far a graph is from being acyclic. When applied to the underlying graph of a hypergraph or a model-theoretic structure (such as a database, a database query, or an instance of a constraint satisfaction problem) it also gives …
-
Tree-based decompositions of graphs on surfaces and applications to the traveling salesman problem
The tree-width and branch-width of a graph are two well-studied examples of parameters that measure how well a given graph can be decomposed into a tree structure. In this thesis we give several results and applications concerning these concepts, in particular if the graph is embedded on a surface. …
-
Symbolic Approaches for Boolean Synthesis
… into factored components that are represented by tree decompositions, with improved performance in realizability checking and witness function synthesis construction. Dynamic programming(DP) framework, which also shows capability and potential in model counting works, improves the operations such …
-
Covariance Selection Quality and Approximation Algorithms
… the quality of the covariance selection for both tree-structured models and non-tree structured models. The second problem we target in this work is to formulate a general framework and algorithms to perform covariance selection. We develop a multistage framework for graphical model approximation …
-
Planning and Execution for Discrete Integration
… in high-level reasoning tools based on graph decompositions, spurred by several competitions. While some existing discrete integration tools (counters) tightly integrate with these low-level computational or high-level reasoning tools, no existing counter is able to leverage both together. In …
-
Establishing a Connection Between Graph Structure, Logic, and Language Theory
The field of graph structure theory was given life by the Graph Minors Project of Robertson and Seymour, which developed many tools for understanding the way graphs relate to each other and culminated in the proof of the Graph Minors Theorem. One area of ongoing research in the field is attempting …