Thesis (Ph. D.)--University of Texas at Austin, 2003. / Supervisor: Raul G. Longoria. Vita. Includes bibliographical references. Also available from UMI.

Thesis (M.S.)--West Virginia University, 2003. / Title from document title page. Document formatted into pages; contains iii, 34 p. : ill. Includes abstract. Includes bibliographical references (p. 33-34).

Not available / text

No description available.

No description available.

No description available.

The probabilistic method in combinatorics is a nonconstructive tool popularized through the work of Paul Erd˝os. Many difficult problems can be solved through a relatively simple application of probability theory that can lead to solutions which are better than known constructive methods. This thesis presents some of the basic tools used throughout the probabilistic method along with some of the applications of the probabilistic method throughout the fields of Ramsey theory, graph theory and other areas of combinatorial analysis. Then the topic of random graphs is covered. The theory of random graphs was founded during the late fifties and early sixties to study questions involving the effect of probability distributions upon graphical properties. This thesis presents some of the basic results involving graph models and graph properties.

The probabilistic method in combinatorics is a nonconstructive tool popularized through the work of Paul Erd˝os. Many difficult problems can be solved through a relatively simple application of probability theory that can lead to solutions which are better than known constructive methods. This thesis presents some of the basic tools used throughout the probabilistic method along with some of the applications of the probabilistic method throughout the fields of Ramsey theory, graph theory and other areas of combinatorial analysis. Then the topic of random graphs is covered. The theory of random graphs was founded during the late fifties and early sixties to study questions involving the effect of probability distributions upon graphical properties. This thesis presents some of the basic results involving graph models and graph properties.

A broadcast on a graph G=(V,E) is a function f : V → {0, ..., diam(G)} that assigns an integer value to each vertex such that, for each v ∈ V , f (v) ≤ e(v), the eccentricity of v. The broadcast number of a graph is the minimum value of Σv∈V f (v) among all broadcasts f with the property that for each vertex x of V, f (v) ≥ d(x, v) for some vertex v having positive f (v). This number is bounded above by both the radius of the graph and its domination number. Graphs for which the broadcast number is equal to the domination number are called 1-cap graphs. We investigate and characterize a class of 1-cap trees. / Graduate

We study group-summarization of probabilistic graphs that naturally arise in social networks, semistructured data, and other applications. Our proposed framework groups the nodes and edges of the graph based on a user selected set of node attributes. We present methods to compute useful graph aggregates without the need to create all of the possible graph-instances of the original probabilistic graph. Also, we present an algorithm for graph summarization based on pure relational (SQL) technology. We analyze our algorithm and practically evaluate its efficiency using an extended Epinions dataset as well as synthetic datasets. The experimental results show the scalability of our algorithm and its efficiency in producing highly compressed summary graphs in reasonable time. / Graduate