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 20 of 69 for “"weighted graphs"”.
-
Stabilizing Weighted Graphs
An edge-weighted graph G = (V,E) is called stable if the value of a maximum-weight matching equals the value of a maximum-weight fractional matching. Stable graphs play an important role in some interesting game theory problems, such as network bargaining games and cooperative matching games, …
-
Limits of weighted graphs
… of countable groups and associated Schreier graphs. In Chapters 1 and 2 we give the motivation and overview for the research presented in this thesis and we establish the basics regarding group actions, especially about Schreier graphs and amenability. Furthermore, we recall the idea of …
-
Mining Frequent Coherent Patterns from Weighted Graphs
Current research on network analysis; such as community detection, pattern mining and many other graph mining application mostly focus on large social or biological networks. Such experiments may find interesting patterns that helps us to understand the unknown relationship within the network. …
-
Can you hear the size of the vertices? An inverse spectral problem of Laplacians on weighted graphs
… (n $-$ 1) eigenvalues and ask for which graphs we can find a set of weights which generate a Laplacian with the spectrum $\Lambda.$ We demonstrate that it is always possible to solve the inverse spectral problem for a three vertex graph. In the case of $K\sb4$, the complete graph on four …
-
Linear systems and Riemann-Roch theory on graphs
Graphs can be viewed as discrete counterparts to algebraic curves, as exemplified by the recent Riemann-Roch formula for integral divisors on multigraphs. We show that for any subring R of the reals, the Riemann-Roch formula can be generalized to R-valued divisors on edge-weighted graphs over R. We …
-
Broadcasting in weighted-vertex graphs
… data to their neighbors. The new model, called weighted-vertex model, comes to have real world applications in parallel computation and satellite terrestrial networks. Broadcasting in weighted-vertex model is a generalized version of classical broadcasting problem, which is NP_Complete. The …
-
Vertex-Weighted Generalizations Of Chromatic Symmetric Functions
… To address this shortcoming we introduce vertex-weighted graphs (G, w) consisting of a graph G and a weight function w : V (G) → N. Then X G extends in a natural way to a new function X (G,w) on vertex-weighted graphs. We demonstrate that X (G,w) satisfies a deletion-contraction relation akin to …
-
The Chromatic MacMahon Function
We examine colorings of weighted graphs. Firstly, we examine the weighted analogue of Stanley’s chromatic symmetric function, and prove that the weighted analogue of Crew’s conjecture is not true. Secondly, we generalize the chromatic symmetric function to the chromatic MacMahon function, and use …
-
A general computational tool for structure synthesis
… However, the Eigensystem method can work for the weighted and both directed and undirected graph, while the Nauty program can only work for the non-weighted and both directed and undirected graph. The cause for this is the different philosophies underlying these two methods. The Nauty program is …
-
Graph Sparsification with Priority
… results involving additive spanners in weighted graphs. An additive $+\beta$ spanner is a subgraph which preserves distances in the original graph up to $+\beta$ additive error; such spanners were largely only studied in unweighted graphs. By generalizing an initialization technique and …
-
Network Tomography
… can be associated to a problem similar to EIT on graphs and indicate how in some sense it may be also associated to the Radon transform on trees. We develop a strategy to determine the weight w for the case of general weighted graphs. We begin by considering relatively simple regions of interest …
-
Texture Synthesis in a Weighted Graph Using Nth-Order Voronoi Diagrams
… generate textures at variable resolutions using weighted graphs. Our method takes a number of input points that exist within a grid-like graph. Using the input points as site node the algorithm then assigns all the nodes in the graph to Voronoi regions by using geodesic rather than Euclidian …
-
Προσεγγιστικά σχήματα, κλίκες, χρώματα και πυκνότεροι υπογράφοι
… algorithms for the densest k-subgraph problem on weighted graphs of maximal degree two, on weighted trees even if the solution is disconnected, and on interval graphs with intersection only between two consecutive cliques. Moreover, we present a polynomial time approximation scheme for the densest …
-
Μελέτη των μηχανισμών διατάραξης της ομαλής κυτταρικής λειτουργίας μέσω της ανακατασκευής γονιδιακών ρυθμιστικών δικτύων
… we developed algorithms for clustering (protein) graphs and gene expression data. Specifically, we implemented a clustering algorithm for weighted graphs towards the extraction of functional modules. The weighted graph was created by using gene expression and protein-protein interaction data. …
-
DISCRETE INVERSE CONDUCTIVITY PROBLEMS ON NETWORKS
… functions and eigensystems of Laplacians for weighted graphs (networks) with and without boundary. We prove the solvability of the Dirichlet and Neumann boundary value problems. We also prove the global uniqueness of the inverse conductivity problem on a network under a suitable monotonicity …
-
On Properties of r<sub>w</sub>-Regular Graphs
… r-regular graph. A graph G is said to be vertex-weighted if all of the vertices are assigned weights. A generalized definition for degree regularity for vertex-weighted graphs can be stated as follows: A vertex-weighted graph is said to be rw-regular if the sum of the weights in the neighborhood …
-
ROBUST TIME-VARYING FORMATION CONTROL WITH ADAPTIVE SUBMODULARITY
… to quantify network robustness are developed for weighted graphs. Formation control is implemented to position nodes relative to virtual leaders. A utility function that encapsulates the sensing, communications, robustness, and dynamics of the NCS is designed and shown to be submodular. Submodular …
-
Finding Independent Transversals Efficiently
… and special independent set problems), hypergraphs (e.g. hypergraph matching), group theory (e.g. generators in linear groups), and theoretical computer science (e.g. job scheduling and other resource allocation problems). However, the proofs of the existence theorems that give the best …
-
Frank-Wolfe Optimization for Dominant Set Clustering
… to represent a clustering problem as an edge-weighted graph, where the nodes and weights represent the objects and pairwise similarities of the problem. Dominant set is a graph-theoretical definition that extends the idea of maximal clique from unweighted to weighted graphs – intuitively it is …
Page 1 of 4