Current Search: Dutton, Ronald (x)
View All Items
 Title
 PARTITIONING A GRAPH IN ALLIANCES AND ITS APPLICATION TO DATA CLUSTERING.
 Creator

HassanShafique, Khurram, Dutton, Ronald, University of Central Florida
 Abstract / Description

Any reasonably large group of individuals, families, states, and parties exhibits the phenomenon of subgroup formations within the group such that the members of each group have a strong connection or bonding between each other. The reasons of the formation of these subgroups that we call alliances differ in different situations, such as, kinship and friendship (in the case of individuals), common economic interests (for both individuals and states), common political interests, and...
Show moreAny reasonably large group of individuals, families, states, and parties exhibits the phenomenon of subgroup formations within the group such that the members of each group have a strong connection or bonding between each other. The reasons of the formation of these subgroups that we call alliances differ in different situations, such as, kinship and friendship (in the case of individuals), common economic interests (for both individuals and states), common political interests, and geographical proximity. This structure of alliances is not only prevalent in social networks, but it is also an important characteristic of similarity networks of natural and unnatural objects. (A similarity network defines the links between two objects based on their similarities). Discovery of such structure in a data set is called clustering or unsupervised learning and the ability to do it automatically is desirable for many applications in the areas of pattern recognition, computer vision, artificial intelligence, behavioral and social sciences, life sciences, earth sciences, medicine, and information theory. In this dissertation, we study a graph theoretical model of alliances where an alliance of the vertices of a graph is a set of vertices in the graph, such that every vertex in the set is adjacent to equal or more vertices inside the set than the vertices outside it. We study the problem of partitioning a graph into alliances and identify classes of graphs that have such a partition. We present results on the relationship between the existence of such a partition and other well known graph parameters, such as connectivity, subgraph structure, and degrees of vertices. We also present results on the computational complexity of finding such a partition. An alliance cover set is a set of vertices in a graph that contains at least one vertex from every alliance of the graph. The complement of an alliance cover set is an alliance free set, that is, a set that does not contain any alliance as a subset. We study the properties of these sets and present tight bounds on their cardinalities. In addition, we also characterize the graphs that can be partitioned into alliance free and alliance cover sets. Finally, we present an approximate algorithm to discover alliances in a given graph. At each step, the algorithm finds a partition of the vertices into two alliances such that the alliances are strongest among all such partitions. The strength of an alliance is defined as a real number p, such that every vertex in the alliance has at least p times more neighbors in the set than its total number of neighbors in the graph). We evaluate the performance of the proposed algorithm on standard data sets.
Show less  Date Issued
 2004
 Identifier
 CFE0000263, ucf:46225
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0000263
 Title
 ALLIANCES IN GRAPHS: PARAMETERIZED ALGORITHMS ANDON PARTITIONING SERIESPARALLEL GRAPHS.
 Creator

Enciso, Rosa, Dutton, Ronald, University of Central Florida
 Abstract / Description

Alliances are used to denote agreements between members of a group with similar interests. Alliances can occur between nations, biological sequences, business cartels, and other entities. The notion of alliances in graphs was first introduced by Kristiansen, Hedetniemi, and Hedetniemi in . A defensive alliance in a graph G=(V,E) is a non empty set S⊆V S where, for all x ∈S, N∩S≥NS. Consequently, every vertex that is a member of a defensive alliance has at least as...
Show moreAlliances are used to denote agreements between members of a group with similar interests. Alliances can occur between nations, biological sequences, business cartels, and other entities. The notion of alliances in graphs was first introduced by Kristiansen, Hedetniemi, and Hedetniemi in . A defensive alliance in a graph G=(V,E) is a non empty set S⊆V S where, for all x ∈S, N∩S≥NS. Consequently, every vertex that is a member of a defensive alliance has at least as many vertices defending it as there are vertices attacking it. Alliances can be used to model a variety of applications such as classification problems, communities in the web distributed protocols, etc . In , Gerber and Kobler introduced the problem of partitioning a graph into strong defensive alliances for the first time as the "Satisfactory Graph Partitioning (SGP)" problem. In his dissertation , Shafique used the problem of partitioning a graph into alliances to model problems in data clustering. Decision problems for several types of alliances and alliance partitions have been shown to be NPcomplete. However, because of their applicability, it is of interest to study methods to overcome the complexity of these problems. In this thesis, we will present a variety of algorithms for finding alliances in different families of graphs with a running time that is polynomial in terms of the size of the input, and allowing exponential running time as a function of a chosen parameter. This study is guided by the theory of parameterized complexity introduced by Rod Downey and Michael Fellows in . In addition to parameterized algorithms for alliance related problems, we study the partition of seriesparallel graphs into alliances. The class of seriesparallel graphs is a special class in graph theory since many problems known to be NPcomplete on general graphs have been shown to have polynomial time algorithms on seriesparallel graphs. For example, the problem of finding a minimum defensive alliance has been shown to have a linear time algorithm when restricted to seriesparallel graphs . Seriesparallel graphs have also been to focus of study in a wide range of applications including CMOS layout and scheduling problems [ML86, Oud97]. Our motivation is driven by clustering properties that can be modeled with alliances. We observe that partitioning seriesparallel graphs into alliances of roughly the same size can be used to partition task graphs to minimize the communication between processors and balance the workload of each processor. We present a characterization of seriesparallel graphs that allow a partition into defensive alliances and a subclass of seriesparallel graphs with a satisfactory partitions.
Show less  Date Issued
 2009
 Identifier
 CFE0002956, ucf:47945
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0002956
 Title
 Finding paths in the rotation graph of binary trees.
 Creator

Rogers, Rodney O., Dutton, Ronald D., Arts and Sciences
 Abstract / Description

University of Central Florida College of Arts and Sciences Thesis; A binary tree coding scheme is a bijection mapping a set of binary trees to a set of integer tuples called codewords. One problem considered in the literature is that of listing the codewords for nnode binary trees, such that successive codewords represent trees differing by a single rotation, a standard operation for rebalancing binary search trees. Then, the codeword sequence corresponds to an Hamiltonian path in the...
Show moreUniversity of Central Florida College of Arts and Sciences Thesis; A binary tree coding scheme is a bijection mapping a set of binary trees to a set of integer tuples called codewords. One problem considered in the literature is that of listing the codewords for nnode binary trees, such that successive codewords represent trees differing by a single rotation, a standard operation for rebalancing binary search trees. Then, the codeword sequence corresponds to an Hamiltonian path in the rotation graph Rn of binary trees, where each node is labelled with an nnode binary tree, and an edge connects two nodes when their trees differ by a single rotation. A related problem is finding a shortest path between two nodes in Rn, which reduces to the problem of transforming one binary tree into another using a minimum number of rotations. Yet a third problem is determining properties of the rotation graph. Our work addresses these three problems.
Show less  Date Issued
 1996
 Identifier
 CFR0000193, ucf:52941
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFR0000193
 Title
 GLOBAL SECURE SETS OF TREES AND GRIDLIKE GRAPHS.
 Creator

Ho, Yiuyu, Dutton, Ronald, University of Central Florida
 Abstract / Description

Let G = (V, E) be a graph and let S be a subset of vertices. The set S is a defensive alliance if for all x in S, N intersect S >= N  S. The concept of defensive alliances was introduced in , primarily for the modeling of nations in times of war, where allied nations are in mutual agreement to join forces if anyone of them is attacked. For a vertex x in a defensive alliance, the number of neighbors of x inside the alliance, plus the vertex x, is at least the number of neighbors of x...
Show moreLet G = (V, E) be a graph and let S be a subset of vertices. The set S is a defensive alliance if for all x in S, N intersect S >= N  S. The concept of defensive alliances was introduced in , primarily for the modeling of nations in times of war, where allied nations are in mutual agreement to join forces if anyone of them is attacked. For a vertex x in a defensive alliance, the number of neighbors of x inside the alliance, plus the vertex x, is at least the number of neighbors of x outside the alliance. In a graph model, the vertices of a graph represent nations and the edges represent country boundaries. Thus, if the nation corresponding to a vertex x is attacked by its neighbors outside the alliance, the attack can be thwarted by x with the assistance of its neighbors in the alliance. In a different subject matter, applies graph theory to model the world wide web, where vertices represent websites and edges represent links between websites. A web community is a subset of vertices of the web graph, such that every vertex in the community has at least as many neighbors in the set as it has outside. So, a web community C satisfies for all x in C, N intersect C > N  C. These sets are very similar to defensive alliances. They are known as strong defensive alliances in the literature of alliances in graphs. Other areas of application for alliances and related topics include classification, data clustering, ecology, business and social networks. Consider the application of modeling nations in times of war introduced in the first paragraph. In a defensive alliance, any attack on a single member of the alliance can be successfully defended. However, as will be demonstrated in Chapter 1, a defensive alliance may not be able to properly defend itself when multiple members are under attack at the same time. The concept of secure sets is introduced in for exactly this purpose. The set S is a secure set if every subset X of S, with the assistance of vertices in S, can successfully defend against simultaneous attacks coming from vertices outside of S. The exact definition of simultaneous attacks and how such attacks may be defended will be provided in Chapter 1. In , the authors presented an interesting characterization for secure sets which resembles the definition of defensive alliances. A nonempty set S is a secure set if and only if for all subset X of S, N intersect S >= N  S (, Theorem 11). The cardinality of a minimum secure set is the security number of G, denoted s(G). A secure set S is a global secure set if it further satisfies N = V. The cardinality of a minimum global secure set of G is the global security number of G, denoted gs(G). In this work, we present results on secure sets and global secure sets. In particular, we present algorithms and bounds for the global security numbers of trees, and the exact values of the global security numbers of paths, cycles and their Cartesian products. Petter Kristiansen, Sandra M. Hedetniemi, and Stephen T. Hedetniemi. "Alliances in graphs." J. Combin. Math. Combin. Comput., 48:157177, 2004. G. W. Flake, S. Lawrence, and C. L. Giles. "Efficient identification of web communities." ACM SIGKDD, pp. 150160, 2000. Robert C. Brigham, Ronald D. Dutton, and Stephen T. Hedetniemi. "Security in graphs." Discrete Appl. Math., 155(13):17081714, 2007.
Show less  Date Issued
 2011
 Identifier
 CFE0003888, ucf:48719
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0003888
 Title
 Techniques for boosting the performance in ContentBased Image Retrieval Systems.
 Creator

Yu, Ning, Hua, Kien, Hughes, Charles, Dutton, Ronald, Wang, ChungChing, University of Central Florida
 Abstract / Description

ContentBased Image Retrieval has been an active research area for decades. In a CBIR system, one or more images are used as query to search for similar images. The similarity is measured on the low level features, such as color, shape, edge, texture. First, each image is processed and visual features are extracted. Therefore each image becomes a point in the feature space. Then, if two images are close to each other in the feature space, they are considered similar. That is, the k nearest...
Show moreContentBased Image Retrieval has been an active research area for decades. In a CBIR system, one or more images are used as query to search for similar images. The similarity is measured on the low level features, such as color, shape, edge, texture. First, each image is processed and visual features are extracted. Therefore each image becomes a point in the feature space. Then, if two images are close to each other in the feature space, they are considered similar. That is, the k nearest neighbors are considered the most similar images to the query image. In this KNearest Neighbor (kNN) model, semantically similar images are assumed to be clustered together in a single neighborhood in the highdimensional feature space. Unfortunately semantically similar images with different appearances are often clustered into distinct neighborhoods, which might scatter in the feature space. Hence, confinement of the search results to a single neighborhood is the latent reason of the low recall rate of typical nearest neighbor techniques. In this dissertation, a new image retrieval technique  the Query Decomposition (QD) model is introduced. QD facilitates retrieval of semantically similar images from multiple neighborhoods in the feature space and hence bridges the semantic gap between the images' lowlevel feature and the highlevel semantic meaning. In the QD model, a query may be decomposed into multiple subqueries based on the user's relevance feedback to cover multiple image clusters which contain semantically similar images. The retrieval results are the k most similar images from multiple discontinuous relevant clusters. To apply the benefit from QD study, a mobile clientside relevance feedback study was conducted. With the proliferation of handheld devices, the demand of multimedia information retrieval on mobile devices has attracted more attention. A relevance feedback information retrieval process usually includes several rounds of query refinement. Each round incurs exchange of tens of images between the mobile device and the server. With limited wireless bandwidth, this process can incur substantial delay making the system unfriendly to use. The Relevance Feedback Support (RFS) structure that was designed in QD technique was adopted for Clientside Relevance Feedback (CRF). Since relevance feedback is done on client side, system response is instantaneous significantly enhancing system usability. Furthermore, since the server is not involved in relevance feedback processing, it is able to support thousands more users simultaneously. As the QD technique improves on the accuracy of CBIR systems, another study, which is called InMemory relevance feedback is studied in this dissertation. In the study, we improved the efficiency of the CBIR systems. Current methods rely on searching the database, stored on disks, in each round of relevance feedback. This strategy incurs long delay making relevance feedback less friendly to the user, especially for very large databases. Thus, scalability is a limitation of existing solutions. The proposed inmemory relevance feedback technique substantially reduce the delay associated with feedback processing, and therefore improve system usability. A dataindependent dimensionalityreduction technique is used to compress the metadata to build a small inmemory database to support relevance feedback operations with minimal disk accesses. The performance of this approach is compared with conventional relevance feedback techniques in terms of computation efficiency and retrieval accuracy. The results indicate that the new technique substantially reduces response time for user feedback while maintaining the quality of the retrieval. In the previous studies, the QD technique relies on a predefined Relevance SupportSupport structure. As the result and user experience indicated that the structure might confine the search range and affect the result. In this dissertation, a novel Multiple Direction Search framework for semiautomatic annotation propagation is studied. In this system, the user interacts with the system to provide example images and the corresponding annotations during the annotation propagation process. In each iteration, the example images are dynamically clustered and the corresponding annotations are propagated separately to each cluster: images in the local neighborhood are annotated. Furthermore, some of those images are returned to the user for further annotation. As the user marks more images, the annotation process goes into multiple directions in the feature space. The query movements can be treated as multiple path navigation. Each path could be further split based on the user's input. In this manner, the system provides accurate annotation assistance to the user  images with the same semantic meaning but different visual characteristics can be handled effectively. From comprehensive experiments on Corel and U. of Washington image databases, the proposed technique shows accuracy and efficiency on annotating image databases.
Show less  Date Issued
 2011
 Identifier
 CFE0004182, ucf:49058
 Format
 Document (PDF)
 PURL
 http://purl.flvc.org/ucf/fd/CFE0004182