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 7 of 7 for “"graph packing"”.
-
Generalized Set and Graph Packing Problems
… communication networks, biological networks, Web graph, among others). Usually a node represents an entity while an edge represents an interaction between two entities. A community arises in a network when two or more entities have common interests, e.g., related proteins, industrial sectors, …
-
Parameterized Approximation Results for Clustering and Graph Packing Problems
The domains of clustering and graph packing have been the focus of extensive research across multiple disciplines, including optimization, machine learning, data mining, computational geometry, and operations research. Many central problems in these domains are known to be NP-hard, prompting the …
-
Sufficient conditions for the existence of specified subgraphs in graphs
A classical problem in combinatorics is, given graphs G and H, to determine if H is a subgraph of G. It is usually computationally complex to determine if H is a subgraph of G. Therefore, we often prove conditions that are sufficient to guarantee that a graph G contains H as a subgraph. In Chapter …
-
Packings and realizations of degree sequences with specified substructures
… of two classical and fundamental areas in graph theory: graph packing and degree sequences. The question of packing degree sequences lies naturally in this intersection, asking when degree sequences have edge-disjoint realizations on the same vertex set. The most significant result in this …
-
Sufficient degree conditions for graph embeddings
… on the sufficient conditions to guarantee one graph being the subgraph of another. In Chapter 2, we discuss list packing, a modification of the idea of graph packing. This is fitting one graph in the complement of another graph. Sauer and Spencer showed a sufficient bound involving maximum …
-
Extremal problems on cycles, packing, and decomposition of graphs
… extremal problems concerning cycles and paths in graphs, graph packing, and graph decomposition. We use “graph” in the general sense, allowing loops and multi-edges. The Chv´atal–Erd˝os Theorem states that every graph whose connectivity is at least its independence number has a spanning cycle. In …
-
Shape Detection by Packing Contours and Regions
… model parts. This thesis presents Contour Packing, a novel framework that detects shapes in a global and integral way, effectively bridging this representation gap. We rst develop a grouping mechanism that organizes individual edges into long contours, by encoding Gestalt factors of …