Current Search:   Dutton, Ronald (x)

View All Items

  • CSV Spreadsheet
(1 - 5 of 5)
PARTITIONING A GRAPH IN ALLIANCES AND ITS APPLICATION TO DATA CLUSTERING
Title
PARTITIONING A GRAPH IN ALLIANCES AND ITS APPLICATION TO DATA CLUSTERING.
Creator
Hassan-Shafique, 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
ALLIANCES IN GRAPHS: PARAMETERIZED ALGORITHMS ANDON PARTITIONING SERIES-PARALLEL GRAPHS
Title
ALLIANCES IN GRAPHS: PARAMETERIZED ALGORITHMS ANDON PARTITIONING SERIES-PARALLEL 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|≥|N-S|. 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|≥|N-S|. 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 NP-complete. 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 series-parallel graphs into alliances. The class of series-parallel graphs is a special class in graph theory since many problems known to be NP-complete on general graphs have been shown to have polynomial time algorithms on series-parallel graphs. For example, the problem of finding a minimum defensive alliance has been shown to have a linear time algorithm when restricted to series-parallel graphs . Series-parallel 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 series-parallel 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 series-parallel graphs that allow a partition into defensive alliances and a subclass of series-parallel 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
Finding paths in the rotation graph of binary trees
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 n-node 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 n-node 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 n-node 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
GLOBAL SECURE SETS OF TREES AND GRID-LIKE GRAPHS
Title
GLOBAL SECURE SETS OF TREES AND GRID-LIKE 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 non-empty 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:157-177, 2004. G. W. Flake, S. Lawrence, and C. L. Giles. "Efficient identification of web communities." ACM SIGKDD, pp. 150-160, 2000. Robert C. Brigham, Ronald D. Dutton, and Stephen T. Hedetniemi. "Security in graphs." Discrete Appl. Math., 155(13):1708-1714, 2007.
Show less
Date Issued
2011
Identifier
CFE0003888, ucf:48719
Format
Document (PDF)
PURL
http://purl.flvc.org/ucf/fd/CFE0003888
Techniques for boosting the performance in Content-Based Image Retrieval Systems
Title
Techniques for boosting the performance in Content-Based Image Retrieval Systems.
Creator
Yu, Ning, Hua, Kien, Hughes, Charles, Dutton, Ronald, Wang, Chung-Ching, University of Central Florida
Abstract / Description
Content-Based 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 moreContent-Based 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 K-Nearest Neighbor (k-NN) model, semantically similar images are assumed to be clustered together in a single neighborhood in the high-dimensional 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' low-level feature and the high-level 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 client-side 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 Client-side 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 In-Memory 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 in-memory relevance feedback technique substantially reduce the delay associated with feedback processing, and therefore improve system usability. A data-independent dimensionality-reduction technique is used to compress the metadata to build a small in-memory 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 pre-defined 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 semi-automatic 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