View All Items

Title: ALMOST REGULAR GRAPHS AND EDGE FACE COLORINGS OF PLANE GRAPHS.
Creator: Macon, Lisa, Zhao, Yue, University of Central Florida
Abstract / Description: Regular graphs are graphs in which all vertices have the same degree. Many properties of these graphs are known. Such graphs play an important role in modeling network configurations where equipment limitations impose a restriction on the maximum number of links emanating from a node. These limitations do not enforce strict regularity, and it becomes interesting to investigate nonregular graphs that are in some sense close to regular. This dissertation explores a particular class of almost...
Show moreRegular graphs are graphs in which all vertices have the same degree. Many properties of these graphs are known. Such graphs play an important role in modeling network configurations where equipment limitations impose a restriction on the maximum number of links emanating from a node. These limitations do not enforce strict regularity, and it becomes interesting to investigate nonregular graphs that are in some sense close to regular. This dissertation explores a particular class of almost regular graphs in detail and defines generalizations on this class. A linear-time algorithm for the creation of arbitrarily large graphs of the discussed class is provided, and a polynomial-time algorithm for recognizing graphs in the class is given. Several invariants for the class are discussed. The edge-face chromatic number χef of a plane graph G is the minimum number of colors that must be assigned to the edges and faces of G such that no edge or face of G receives the same color as an edge or face with which it is incident or adjacent. A well-known result for the upper bound of χef exists for graphs with maximum degree Δ ≥ 10. We present a tight upper bound for plane graphs with Δ = 9.
Show less
Date Issued: 2009
Identifier: CFE0002507, ucf:47684
Format: Document (PDF)
PURL: http://purl.flvc.org/ucf/fd/CFE0002507

Title: On Randic Energy of Graphs.
Creator: Burns, Brittany, Mohapatra, Ram, Song, Zixia, Brennan, Joseph, University of Central Florida
Abstract / Description: In this research, we explore the subject of graph energy. We first discuss the connections between linear algebra and graph theory and review some important definitions and facts of these two fields. We introduce graph energy and provide some historical perspectives on the subject. Known results of graph energy are also mentioned and some relevant results are proven. We discuss some applications of graph energy in the physical sciences. Then, Randic energy is defined and results are given and...
Show moreIn this research, we explore the subject of graph energy. We first discuss the connections between linear algebra and graph theory and review some important definitions and facts of these two fields. We introduce graph energy and provide some historical perspectives on the subject. Known results of graph energy are also mentioned and some relevant results are proven. We discuss some applications of graph energy in the physical sciences. Then, Randic energy is defined and results are given and proved for specific families of graphs. We focus on simple, connected graphs that are commonly studied in graph theory. Also, the Laplacian energy of a graph is defined. We then examine the connections between the different types of energies for graphs, beginning with graph energy and Randic energy, followed by Laplacian energy and Randic energy. In our results chapter, we introduce the Petersen graph and calculate the Randic energy of this graph. We also define Stacked-Book graphs and perform some calculations on these graphs. From these calculations, we form a conjecture and discuss some details on how to proceed with the proof of this conjecture. Finally, we summarize our work and details are provided on how this research can be continued.
Show less
Date Issued: 2016
Identifier: CFE0006273, ucf:51043
Format: Document (PDF)
PURL: http://purl.flvc.org/ucf/fd/CFE0006273

Title: H(&)#252;ckel Energy of a Graph: Its Evolution From Quantum Chemistry to Mathematics.
Creator: Zimmerman, Steven, Mohapatra, Ram, Song, Zixia, Brigham, Robert, University of Central Florida
Abstract / Description: The energy of a graph began with German physicist, Erich H(&)#252;ckel's 1931 paper, QuantenttheoretischeBeitr(&)#228;ge zum Benzolproblem. His work developed a method for computing thebinding energy of the ?-electrons for a certain class of organic molecules. The vertices of thegraph represented the carbon atoms while the single edge between each pair of distinct verticesrepresented the hydrogen bonds between the carbon atoms. In turn, the chemical graphswere represented by an n (&)#215; n...
Show moreThe energy of a graph began with German physicist, Erich H(&)#252;ckel's 1931 paper, QuantenttheoretischeBeitr(&)#228;ge zum Benzolproblem. His work developed a method for computing thebinding energy of the ?-electrons for a certain class of organic molecules. The vertices of thegraph represented the carbon atoms while the single edge between each pair of distinct verticesrepresented the hydrogen bonds between the carbon atoms. In turn, the chemical graphswere represented by an n (&)#215; n matrix used in solving Schr(&)#246;dinger's eigenvalue/eigenvectorequation. The sum of the absolute values of these graph eigenvalues represented the total?-electron energy. The criteria for constructing these chemical graphs and the chemical interpretationsof all the quantities involved made up the H(&)#252;ckel Molecular Orbital theoryor HMO theory. In this paper, we will show how the chemical interpretation of H(&)#252;ckel'sgraph energy evolved to a mathematical interpretation of graph energy that Ivan Gutmanprovided for us in his famous 1978 definition of the energy of a graph. Next, we will presentCharles Coulson's 1940 theorem that expresses the energy of a graph as a contour integraland prove some of its corollaries. These corollaries allow us to order the energies of acyclicand bipartite graphs by the coefficients of their characteristic polynomial. Following Coulson'stheorem and its corollaries we will look at McClelland's first theorem on the boundsfor the energy of a graph. In the corollaries that follow McClelland's 1971 theorem, we willprove the corollaries that show a direct variation between the energy of a graph and thenumber of its vertices and edges. Finally, we will see how this relationship led to Gutman'sconjecture that the complete graph on n vertices has maximal energy. Although this wasdisproved by Chris Godsil in 1981, we will provide an independent counterexample with thehelp of the software, Maple 13.
Show less
Date Issued: 2011
Identifier: CFE0004184, ucf:49027
Format: Document (PDF)
PURL: http://purl.flvc.org/ucf/fd/CFE0004184

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

Title: ATTACKS ON DIFFICULT INSTANCES OF GRAPH ISOMORPHISM: SEQUENTIAL AND PARALLEL ALGORITHMS.
Creator: Tener, Greg, Deo, Narsingh, University of Central Florida
Abstract / Description: The graph isomorphism problem has received a great deal of attention on both theoretical and practical fronts. However, a polynomial algorithm for the problem has yet to be found. Even so, the best of the existing algorithms perform well in practice; so well that it is challenging to find hard instances for them. The most efficient algorithms, for determining if a pair of graphs are isomorphic, are based on the individualization-refinement paradigm, pioneered by Brendan McKay in 1981 with his...
Show moreThe graph isomorphism problem has received a great deal of attention on both theoretical and practical fronts. However, a polynomial algorithm for the problem has yet to be found. Even so, the best of the existing algorithms perform well in practice; so well that it is challenging to find hard instances for them. The most efficient algorithms, for determining if a pair of graphs are isomorphic, are based on the individualization-refinement paradigm, pioneered by Brendan McKay in 1981 with his algorithm nauty. Nauty and various improved descendants of nauty, such as bliss and saucy, solve the graph isomorphism problem by determining a canonical representative for each of the graphs. The graphs are isomorphic if and only if their canonical representatives are identical. These algorithms also detect the symmetries in a graph which are used to speed up the search for the canonical representative--an approach that performs well in practice. Yet, several families of graphs have been shown to exist which are hard for nauty-like algorithms. This dissertation investigates why these graph families pose difficulty for individualization-refinement algorithms and proposes several techniques for circumventing these limitations. The first technique we propose addresses a fundamental problem pointed out by Miyazaki in 1993. He constructed a family of colored graphs which require exponential time for nauty (and nauty's improved descendants). We analyze Miyazaki's construction to determine the source of difficulty and identify a solution. We modify the base individualization-refinement algorithm by exploiting the symmetries discovered in a graph to guide the search for its canonical representative. This is accomplished with the help of a novel data structure called a guide tree. As a consequence, colored Miyazaki graphs are processed in polynomial time--thus obviating the only known exponential upper-bound on individualization-refinement algorithms (which has stood for the last 16 years). The preceding technique can only help if a graph has enough symmetry to exploit. It cannot be used for another family of hard graphs that have a high degree of regularity, but possess few actual symmetries. To handle these instances, we introduce an adaptive refinement method which utilizes the guide-tree data structure of the preceding technique to use a stronger vertex-invariant, but only when needed. We show that adaptive refinement is very effective, and it can result in dramatic speedups. We then present a third technique ideally suited for large graphs with a preponderance of sparse symmetries. A method was devised by Darga et al. for dealing with these large and highly symmetric graphs, which can reduce runtime by an order of magnitude. We explain the method and show how to incorporate it into our algorithm. Finally, we develop and implement a parallel algorithm for detecting the symmetries in, and finding a canonical representative of a graph. Our novel parallel algorithm divides the search for the symmetries and canonical representative among each processor, allowing for a high degree of scalability. The parallel algorithm is benchmarked on the hardest problem instances, and shown to be effective in subdividing the search space.
Show less
Date Issued: 2009
Identifier: CFE0002894, ucf:48018
Format: Document (PDF)
PURL: http://purl.flvc.org/ucf/fd/CFE0002894

Title: Interval Edge-Colorings of Graphs.
Creator: Foster, Austin, Song, Zixia, Reid, Michael, Brennan, Joseph, University of Central Florida
Abstract / Description: A proper edge-coloring of a graph G by positive integers is called an interval edge-coloring if the colors assigned to the edges incident to any vertex in G are consecutive (i.e., those colors form an interval of integers). The notion of interval edge-colorings was first introduced by Asratian and Kamalian in 1987, motivated by the problem of finding compact school timetables. In 1992, Hansen described another scenario using interval edge-colorings to schedule parent-teacher conferences so...
Show moreA proper edge-coloring of a graph G by positive integers is called an interval edge-coloring if the colors assigned to the edges incident to any vertex in G are consecutive (i.e., those colors form an interval of integers). The notion of interval edge-colorings was first introduced by Asratian and Kamalian in 1987, motivated by the problem of finding compact school timetables. In 1992, Hansen described another scenario using interval edge-colorings to schedule parent-teacher conferences so that every person's conferences occur in consecutive slots. A solution exists if and only if the bipartite graph with vertices for parents and teachers, and edges for the required meetings, has an interval edge-coloring.A well-known result of Vizing states that for any simple graph $G$, $\chi'(G) \leq \Delta(G) + 1$, where $\chi'(G)$ and $\Delta(G)$ denote the edge-chromatic number and maximum degree of $G$, respectively. A graph $G$ is called class 1 if $\chi'(G) = \Delta(G)$, and class 2 if $\chi'(G) = \Delta(G) + 1$. One can see that any graph admitting an interval edge-coloring must be of class 1, and thus every graph of class 2 does not have such a coloring.Finding an interval edge-coloring of a given graph is hard. In fact, it has been shown that determining whether a bipartite graph has an interval edge-coloring is NP-complete. In this thesis, we survey known results on interval edge-colorings of graphs, with a focus on the progress of $(a, b)$-biregular bipartite graphs. Discussion of related topics and future work is included at the end. We also give a new proof of Theorem 3.15 on the existence of proper path factors of $(3, 4)$-biregular graphs. Finally, we obtain a new result, Theorem 3.18, which states that if a proper path factor of any $(3, 4)$-biregular graph has no path of length 8, then it contains paths of length 6 only. The new result we obtained and the method we developed in the proof of Theorem 3.15 might be helpful in attacking the open problems mentioned in the Future Work section of Chapter 5.
Show less
Date Issued: 2016
Identifier: CFE0006301, ucf:51609
Format: Document (PDF)
PURL: http://purl.flvc.org/ucf/fd/CFE0006301

Title: GALLAI-RAMSEY NUMBERS FOR C7 WITH MULTIPLE COLORS.
Creator: Bruce, Dylan, Song, Zi-Xia, University of Central Florida
Abstract / Description: The core idea of Ramsey theory is that complete disorder is impossible. Given a large structure, no matter how complex it is, we can always find a smaller substructure that has some sort of order. One view of this problem is in edge-colorings of complete graphs. For any graphs G, H1, ..., Hk, we write G ? (H1, ..., Hk), or G ? (H)k when H1 = �� = Hk = H, if every k-edge-coloring of G contains a monochromatic Hi in color i for some i ? {1,...,k}. The Ramsey number rk(H1, ..., Hk) is the...
Show moreThe core idea of Ramsey theory is that complete disorder is impossible. Given a large structure, no matter how complex it is, we can always find a smaller substructure that has some sort of order. One view of this problem is in edge-colorings of complete graphs. For any graphs G, H1, ..., Hk, we write G ? (H1, ..., Hk), or G ? (H)k when H1 = �� = Hk = H, if every k-edge-coloring of G contains a monochromatic Hi in color i for some i ? {1,...,k}. The Ramsey number rk(H1, ..., Hk) is the minimum integer n such that Kn ? (H1, ..., Hk), where Kn is the complete graph on n vertices. Computing rk(H1, ..., Hk) is a notoriously difficult problem in combinatorics. A weakening of this problem is to restrict ourselves to Gallai colorings, that is, edge-colorings with no rainbow triangles. From this we define the Gallai-Ramsey number grk(K3,G) as the minimum integer n such that either Kn contains a rainbow triangle, or Kn ? (G)k . In this thesis, we determine the Gallai-Ramsey numbers for C7 with multiple colors. We believe the method we developed can be applied to find grk(K3, C2n+1) for any integer n ? 2, where C2n+1 denotes a cycle on 2n + 1 vertices.
Show less
Date Issued: 2017
Identifier: CFH2000264, ucf:46025
Format: Document (PDF)
PURL: http://purl.flvc.org/ucf/fd/CFH2000264

Title: Efficient String Graph Construction Algorithm.
Creator: Morshed, S.M. Iqbal, Yooseph, Shibu, Zhang, Shaojie, Valliyil Thankachan, Sharma, University of Central Florida
Abstract / Description: In the field of genome assembly research where assemblers are dominated by de Bruijn graph-based approaches, string graph-based assembly approach is getting more attention because of its ability to losslessly retain information from sequence data. Despite the advantages provided by a string graph in repeat detection and in maintaining read coherence, the high computational cost for constructing a string graph hinders its usability for genome assembly. Even though different algorithms have...
Show moreIn the field of genome assembly research where assemblers are dominated by de Bruijn graph-based approaches, string graph-based assembly approach is getting more attention because of its ability to losslessly retain information from sequence data. Despite the advantages provided by a string graph in repeat detection and in maintaining read coherence, the high computational cost for constructing a string graph hinders its usability for genome assembly. Even though different algorithms have been proposed over the last decade for string graph construction, efficiency is still a challenge due to the demand for processing a large amount of sequence data generated by NGS technologies. Therefore, in this thesis, we provide a novel, linear time and alphabet-size-independent algorithm SOF which uses the property of irreducible edges and transitive edges to efficiently construct string graph from an overlap graph. Experimental results show that SOF is at least 2 times faster than the string graph construction algorithm provided in SGA, one of the most popular string graph-based assembler, while maintaining almost the same memory footprint as SGA. Moreover, the availability of SOF as a subprogram in the SGA assembly pipeline will give user facilities to access the preprocessing and postprocessing steps for genome assembly provided in SGA.
Show less
Date Issued: 2019
Identifier: CFE0007504, ucf:52635
Format: Document (PDF)
PURL: http://purl.flvc.org/ucf/fd/CFE0007504

Title: Coloring graphs with forbidden minors.
Creator: Rolek, Martin, Song, Zixia, Brennan, Joseph, Reid, Michael, Zhao, Yue, DeMara, Ronald, University of Central Florida
Abstract / Description: A graph H is a minor of a graph G if H can be obtained from a subgraph of G by contracting edges. My research is motivated by the famous Hadwiger's Conjecture from 1943 which states that every graph with no Kt-minor is (t - 1)-colorable. This conjecture has been proved true for t ? 6, but remains open for all t ? 7. For t = 7, it is not even yet known if a graph with no K7-minor is 7-colorable. We begin by showing that every graph with no K_t-minor is (2t - 6)-colorable for t = 7, 8, 9, in...
Show moreA graph H is a minor of a graph G if H can be obtained from a subgraph of G by contracting edges. My research is motivated by the famous Hadwiger's Conjecture from 1943 which states that every graph with no Kt-minor is (t - 1)-colorable. This conjecture has been proved true for t ? 6, but remains open for all t ? 7. For t = 7, it is not even yet known if a graph with no K7-minor is 7-colorable. We begin by showing that every graph with no K_t-minor is (2t - 6)-colorable for t = 7, 8, 9, in the process giving a shorter and computer-free proof of the known results for t = 7, 8. We also show that this result extends to larger values of t if Mader's bound for the extremal function for Kt-minors is true. Additionally, we show that any graph with no K8?-minor is 9-colorable, and any graph with no K8?-minor is 8-colorable. The Kempe-chain method developed for our proofs of the above results may be of independent interest. We also use Mader's H-Wege theorem to establish some sufficient conditions for a graph to contain a K8-minor.Another motivation for my research is a well-known conjecture of Erd?s and Lov(&)#225;sz from 1968, the Double-Critical Graph Conjecture. A connected graph G is double-critical if for all edges xy ? E(G), ?(G - x - y) = ?(G) - 2. Erd?s and Lov(&)#225;sz conjectured that the only double-critical t-chromatic graph is the complete graph Kt. This conjecture has been show to be true for t ? 5 and remains open for t ? 6. It has further been shown that any non-complete, double-critical, t-chromatic graph contains Kt as a minor for t ? 8. We give a shorter proof of this result for t = 7, a computer-free proof for t = 8, and extend the result to show that G contains a K9-minor for all t ? 9. Finally, we show that the Double-Critical Graph Conjecture is true for double-critical graphs with chromatic number t ? 8 if such graphs are claw-free.
Show less
Date Issued: 2017
Identifier: CFE0006649, ucf:51227
Format: Document (PDF)
PURL: http://purl.flvc.org/ucf/fd/CFE0006649

Title: Hilbert Series of Graphs, Hypergraphs, and Monomial Ideals.
Creator: Trainor, Kyle, Brennan, Joseph, Song, Zixia, Martin, Heath, Morey, Susan, Wocjan, Pawel, University of Central Florida
Abstract / Description: In this dissertation, identities for Hilbert series of quotients of polynomial rings by monomial ideals are explored, beginning in the contexts of graph and hypergraph rings and later generalizing to general monomial ideals. These identities are modeled after constructive identities from graph theory, and can thus be used to construct Hilbert series iteratively from those of smaller algebraic structures.
Date Issued: 2018
Identifier: CFE0007258, ucf:52176
Format: Document (PDF)
PURL: http://purl.flvc.org/ucf/fd/CFE0007258

Title: Computing a diameter-constrained minimum spanning tree.
Creator: Abdalla, Ayman Mahmoud, Deo, Narsingh, Engineering and Computer Science
Abstract / Description: University of Central Florida College of Engineering Thesis; In numerous practical applications, it is necessary to find the smallest possible tree with a bounded diameter. A diameter-constrained minimum spanning tree (DCMST) of a given undirected, edge-weighted graph, G, is the smallest-weight spanning tree of all spanning trees of G which contain no path with more than k edges, where k is a given positive integer. The problem of finding a DCMST is NP-complete for all values of k; 4
Show moreUniversity of Central Florida College of Engineering Thesis; In numerous practical applications, it is necessary to find the smallest possible tree with a bounded diameter. A diameter-constrained minimum spanning tree (DCMST) of a given undirected, edge-weighted graph, G, is the smallest-weight spanning tree of all spanning trees of G which contain no path with more than k edges, where k is a given positive integer. The problem of finding a DCMST is NP-complete for all values of k; 4 <= k <= (n - 2), except when all edge-weights are identical. A DCMST is essential for the efficiency of various distributed mutual exclusion algorithms, where it can minimize the number of messages communicated among processors per critical section. It is also useful in linear lightwave networks, where it can minimize interference in the network by limiting the traffic in the network lines. Another practical application requiring a DCMST arises in data compression, where some algorithms compress a file utilizing a data-structure, and decompress a path in the tree to access a record A DCMST helps such algorithm to be fast without sacrificing a lot of storage storage space.
Show less
Date Issued: 2001
Identifier: CFR0002215, ucf:52914
Format: Document (PDF)
PURL: http://purl.flvc.org/ucf/fd/CFR0002215

Title: ON SATURATION NUMBERS OF RAMSEY-MINIMAL GRAPHS.
Creator: Davenport, Hunter M, Song, Zi-Xia, University of Central Florida
Abstract / Description: Dating back to the 1930's, Ramsey theory still intrigues many who study combinatorics. Roughly put, it makes the profound assertion that complete disorder is impossible. One view of this problem is in edge-colorings of complete graphs. For forbidden graphs H1,...,Hk and a graph G, we write G "arrows" (H1,...,Hk) if every k-edge-coloring of G contains a monochromatic copy of Hi in color i for some i=1,2,...,k. If c is a (red, blue)-edge-coloring of G, we say c is a bad coloring if G contains...
Show moreDating back to the 1930's, Ramsey theory still intrigues many who study combinatorics. Roughly put, it makes the profound assertion that complete disorder is impossible. One view of this problem is in edge-colorings of complete graphs. For forbidden graphs H1,...,Hk and a graph G, we write G "arrows" (H1,...,Hk) if every k-edge-coloring of G contains a monochromatic copy of Hi in color i for some i=1,2,...,k. If c is a (red, blue)-edge-coloring of G, we say c is a bad coloring if G contains no red K3or blue K1,t under c. A graph G is (H1,...,Hk)-Ramsey-minimal if G arrows (H1,...,Hk) but no proper subgraph of G has this property. Given a family F of graphs, we say that a graph G is F-saturated if no member of F is a subgraph of G, but for any edge xy not in E(G), G + xy contains a member of F as a subgraph. Letting Rmin(K3, K1,t) be the family of (K3,K1,t)-Ramsey minimal graphs, we study the saturation number, denoted sat(n,Rmin(K3,K1,t)), which is the minimum number of edges among all Rmin(K3,K1,t)-saturated graphs on n vertices. We believe the methods and constructions developed in this thesis will be useful in studying the saturation numbers of (K4,K1,t)-saturated graphs.
Show less
Date Issued: 2018
Identifier: CFH2000291, ucf:45881
Format: Document (PDF)
PURL: http://purl.flvc.org/ucf/fd/CFH2000291

Title: A SPARSE PROGRAM DEPENDENCE GRAPH FOR OBJECT ORIENTED PROGRAMMING LANGUAGES.
Creator: Garfield, Keith, Hughes, Charles, University of Central Florida
Abstract / Description: The Program Dependence Graph (PDG) has achieved widespread acceptance as a useful tool for software engineering, program analysis, and automated compiler optimizations. This thesis presents the Sparse Object Oriented Program Dependence Graph (SOOPDG), a formalism that contains elements of traditional PDG's adapted to compactly represent programs written in object-oriented languages such as Java. This formalism is called sparse because, in contrast to other OO and Java-specific adaptations...
Show moreThe Program Dependence Graph (PDG) has achieved widespread acceptance as a useful tool for software engineering, program analysis, and automated compiler optimizations. This thesis presents the Sparse Object Oriented Program Dependence Graph (SOOPDG), a formalism that contains elements of traditional PDG's adapted to compactly represent programs written in object-oriented languages such as Java. This formalism is called sparse because, in contrast to other OO and Java-specific adaptations of PDG's, it introduces few node types and no new edge types beyond those used in traditional dependence-based representations. This results in correct program representations using smaller graph structures and simpler semantics when compared to other OO formalisms. We introduce the Single Flow to Use (SFU) property which requires that exactly one definition of each variable be available for each use. We demonstrate that the SOOPDG, with its support for the SFU property coupled with a higher order rewriting semantics, is sufficient to represent static Java-like programs and dynamic program behavior. We present algorithms for creating SOOPDG representations from program text, and describe graph rewriting semantics. We also present algorithms for common static analysis techniques such as program slicing, inheritance analysis, and call chain analysis. We contrast the SOOPDG with two previously published OO graph structures, the Java System Dependence Graph and the Java Software Dependence Graph. The SOOPDG results in comparatively smaller static representations of programs, cleaner graph semantics, and potentially more accurate program analysis. Finally, we introduce the Simulation Dependence Graph (SDG). The SDG is a related representation that is developed specifically to represent simulation systems, but is extensible to more general component-based software design paradigms. The SDG allows formal reasoning about issues such as component composition, a property critical to the creation and analysis of complex simulation systems and component-based design systems.
Show less
Date Issued: 2006
Identifier: CFE0001499, ucf:47077
Format: Document (PDF)
PURL: http://purl.flvc.org/ucf/fd/CFE0001499

Title: EXPLANATIONS IN CONTEXTUAL GRAPHS:A SOLUTION TO ACCOUNTABILITY INKNOWLEDGE BASED SYSTEMS.
Creator: Sherwell, Brian, Gonzalez, Avelino, University of Central Florida
Abstract / Description: In order for intelligent systems to be a viable and utilized tool, a user must be able to understand how the system comes to a decision. Without understanding how the system arrived at an answer, a user will be less likely to trust its decision. One way to increase a user's understanding of how the system functions is by employing explanations to account for the output produced. There have been attempts to explain intelligent systems over the past three decades. However, each attempt has had...
Show moreIn order for intelligent systems to be a viable and utilized tool, a user must be able to understand how the system comes to a decision. Without understanding how the system arrived at an answer, a user will be less likely to trust its decision. One way to increase a user's understanding of how the system functions is by employing explanations to account for the output produced. There have been attempts to explain intelligent systems over the past three decades. However, each attempt has had shortcomings that separated the logic used to produce the output and that used to produce the explanation. By using the representational paradigm of Contextual Graphs, it is proposed that explanations can be produced to overcome these shortcomings. Two different temporal forms of explanations are proposed, a pre-explanation and a post-explanation. The pre-explanation is intended to help the user understand the decision making process. The post-explanation is intended to help the user understand how the system arrived at a final decision. Both explanations are intended to help the user gain a greater understanding of the logic used to compute the system's output, and thereby enhance the system's credibility and utility. A prototype system is constructed to be used as a decision support tool in a National Science Foundation research program. The researcher has spent the last year at the NSF collecting the knowledge implemented in the prototype system.
Show less
Date Issued: 2005
Identifier: CFE0000713, ucf:46601
Format: Document (PDF)
PURL: http://purl.flvc.org/ucf/fd/CFE0000713

Title: FINDING DUD VERTICES IN DEFENSIVE ALLIANCES AND SECURE SETS USING COMPUTATIONAL TOOLS.
Creator: Worley, George, Zhao, Yue, University of Central Florida
Abstract / Description: Defensive alliances are a way of using graphs to model the defense of resources (people, buildings, countries, etc.) against attacks where the number of potential attackers against each resource is known. The initial study of defensive alliances focused on questions of minimal defensive alliances in a graph and the minimum possible size of a defensive alliance in a graph, but in order to apply defensive alliances in modeling real-world situations, additional considerations are important. In...
Show moreDefensive alliances are a way of using graphs to model the defense of resources (people, buildings, countries, etc.) against attacks where the number of potential attackers against each resource is known. The initial study of defensive alliances focused on questions of minimal defensive alliances in a graph and the minimum possible size of a defensive alliance in a graph, but in order to apply defensive alliances in modeling real-world situations, additional considerations are important. In particular, since each vertex in a defensive alliance represents some real-world object that has a cost associated with remaining in the defensive alliance, it is important to consider the value each vertex adds to the defensive alliance. In this thesis we consider a method of assessing the efficiency of a defensive alliance, including the special case of secure sets.
Show less
Date Issued: 2011
Identifier: CFE0004010, ucf:49166
Format: Document (PDF)
PURL: http://purl.flvc.org/ucf/fd/CFE0004010

Title: Analysis of Commutativity with state-chart graph representation of concurrent programs.
Creator: Debnath, Kishore, Dechev, Damian, Leavens, Gary, Bassiouni, Mostafa, University of Central Florida
Abstract / Description: We present a new approach to check for Commutativity in concurrent programs from their run-time state-chart graphs. Two operations are said to be commutative if changing the order of their execution do not change the resultant effect on the working object. Commutative property is capable of boosting performance in concurrent transactions such that transactional concurrency is comparable to a non-blocking linearizable version of a similar data structure type. Transactional concurrency is a...
Show moreWe present a new approach to check for Commutativity in concurrent programs from their run-time state-chart graphs. Two operations are said to be commutative if changing the order of their execution do not change the resultant effect on the working object. Commutative property is capable of boosting performance in concurrent transactions such that transactional concurrency is comparable to a non-blocking linearizable version of a similar data structure type. Transactional concurrency is a technique that analyses object semantics, as object states, to determine conflicts and recovery between conflicting operations. Processes that commute at object level can be executed concurrently at transaction level without conflicting with one another. In our approach we generate graphs by tracking run-time execution of concurrent program and representing object states in all possible thread interleavings as states and transitions. Using state-chart notations, we capture the object states at each execution step and compare their states before and after transitions as processed by a known set of operations reordered in different ways. Considering the non-deterministic nature of concurrent programs, we exhaustively capture program states during method invocation, method response, atomic instruction execution, etc., for determining commutativity. This helps user to examine state transitions at a thread level granularity, across all possible interleavings. With this methodology user can not only verify commutativity, but also can visually check ways in which functions commute at object level, which is an edge over current state-of-the art tools. The object level commutative information helps in identifying faulty implementations and performance improving considerations. We use a graph database to represent state nodes that further assists to check for other concurrency properties using cypher queries.
Show less
Date Issued: 2016
Identifier: CFE0006290, ucf:51608
Format: Document (PDF)
PURL: http://purl.flvc.org/ucf/fd/CFE0006290

Title: ALGORITHMS FOR DISCOVERING COMMUNITIES IN COMPLEX NETWORKS.
Creator: Balakrishnan, Hemant, Deo, Narsingh, University of Central Florida
Abstract / Description: It has been observed that real-world random networks like the WWW, Internet, social networks, citation networks, etc., organize themselves into closely-knit groups that are locally dense and globally sparse. These closely-knit groups are termed communities. Nodes within a community are similar in some aspect. For example in a WWW network, communities might consist of web pages that share similar contents. Mining these communities facilitates better understanding of their evolution and...
Show moreIt has been observed that real-world random networks like the WWW, Internet, social networks, citation networks, etc., organize themselves into closely-knit groups that are locally dense and globally sparse. These closely-knit groups are termed communities. Nodes within a community are similar in some aspect. For example in a WWW network, communities might consist of web pages that share similar contents. Mining these communities facilitates better understanding of their evolution and topology, and is of great theoretical and commercial significance. Community related research has focused on two main problems: community discovery and community identification. Community discovery is the problem of extracting all the communities in a given network, whereas community identification is the problem of identifying the community, to which, a given set of nodes belong. We make a comparative study of various existing community-discovery algorithms. We then propose a new algorithm based on bibliographic metrics, which addresses the drawbacks in existing approaches. Bibliographic metrics are used to study similarities between publications in a citation network. Our algorithm classifies nodes in the network based on the similarity of their neighborhoods. One of the drawbacks of the current community-discovery algorithms is their computational complexity. These algorithms do not scale up to the enormous size of the real-world networks. We propose a hash-table-based technique that helps us compute the bibliometric similarity between nodes in O(m ?) time. Here m is the number of edges in the graph and ?, the largest degree. Next, we investigate different centrality metrics. Centrality metrics are used to portray the importance of a node in the network. We propose an algorithm that utilizes centrality metrics of the nodes to compute the importance of the edges in the network. Removal of the edges in ascending order of their importance breaks the network into components, each of which represent a community. We compare the performance of the algorithm on synthetic networks with a known community structure using several centrality metrics. Performance was measured as the percentage of nodes that were correctly classified. As an illustration, we model the ucf.edu domain as a web graph and analyze the changes in its properties like densification power law, edge density, degree distribution, diameter, etc., over a five-year period. Our results show super-linear growth in the number of edges with time. We observe (and explain) that despite the increase in average degree of the nodes, the edge density decreases with time.
Show less
Date Issued: 2006
Identifier: CFE0001473, ucf:47085
Format: Document (PDF)
PURL: http://purl.flvc.org/ucf/fd/CFE0001473

Title: AUTOMATIC ANNOTATION OF DATABASE IMAGES FOR QUERY-BY-CONCEPT.
Creator: Hiransakolwong, Nualsawat, Hua, kien A., University of Central Florida
Abstract / Description: As digital images become ubiquitous in many applications, the need for efficient and effective retrieval techniques is more demanding than ever. Query by Example (QBE) and Query by Concept (QBC) are among the most popular query models. The former model accepts example images as queries and searches for similar ones based on low-level features such as colors and textures. The latter model allows queries to be expressed in the form of high-level semantics or concept words, such as "boat" or ...
Show moreAs digital images become ubiquitous in many applications, the need for efficient and effective retrieval techniques is more demanding than ever. Query by Example (QBE) and Query by Concept (QBC) are among the most popular query models. The former model accepts example images as queries and searches for similar ones based on low-level features such as colors and textures. The latter model allows queries to be expressed in the form of high-level semantics or concept words, such as "boat" or "car," and finds images that match the specified concepts. Recent research has focused on the connections between these two models and attempts to close the semantic-gap between them. This research involves finding the best method that maps a set of low-level features into high-level concepts. Automatic annotation techniques are investigated in this dissertation to facilitate QBC. In this approach, sets of training images are used to discover the relationship between low-level features and predetermined high-level concepts. The best mapping with respect to the training sets is proposed and used to analyze images, annotating them with the matched concept words. One principal difference between QBE and QBC is that, while similarity matching in QBE must be done at the query time, QBC performs concept exploration off-line. This difference allows QBC techniques to shift the time-consuming task of determining similarity away from the query time, thus facilitating the additional processing time required for increasingly accurate matching. Consequently, QBC's primary design objective is to achieve accurate annotation within a reasonable processing time. This objective is the guiding principle in the design of the following proposed methods which facilitate image annotation: 1.A novel dynamic similarity function. This technique allows users to query with multiple examples: relevant, irrelevant or neutral. It uses the range distance in each group to automatically determine weights in the distance function. Among the advantages of this technique are higher precision and recall rates with fast matching time. 2.Object recognition based on skeletal graphs. The topologies of objects' skeletal graphs are captured and compared at the node level. Such graph representation allows preservation of the skeletal graph's coherence without sacrificing the flexibility of matching similar portions of graphs across different levels. The technique is robust to translation, scaling, and rotation invariants at object level. This technique achieves high precision and recall rates with reasonable matching time and storage space. 3.ASIA (Automatic Sampling-based Image Annotation) is a technique based on a new sampling-based matching framework allowing users to identify their area of interest. ASIA eliminates noise, or irrelevant areas of the image. ASIA is robust to translation, scaling, and rotation invariants at the object level. This technique also achieves high precision and recall rates. While the above techniques may not be the fastest when contrasted with some other recent QBE techniques, they very effectively perform image annotation. The results of applying these processes are accurately annotated database images to which QBC may then be applied. The results of extensive experiments are presented to substantiate the performance advantages of the proposed techniques and allow them to be compared with other recent high-performance techniques. Additionally, a discussion on merging the proposed techniques into a highly effective annotation system is also detailed.
Show less
Date Issued: 2004
Identifier: CFE0000262, ucf:46239
Format: Document (PDF)
PURL: http://purl.flvc.org/ucf/fd/CFE0000262

Title: ANALYZING THE COMMUNITY STRUCTURE OF WEB-LIKE NETWORKS: MODELS AND ALGORITHMS.
Creator: Cami, Aurel, Deo, Narsingh, University of Central Florida
Abstract / Description: This dissertation investigates the community structure of web-like networks (i.e., large, random, real-life networks such as the World Wide Web and the Internet). Recently, it has been shown that many such networks have a locally dense and globally sparse structure with certain small, dense subgraphs occurring much more frequently than they do in the classical Erdös-Rényi random graphs. This peculiarity--which is commonly referred to as community structure--has been observed in...
Show moreThis dissertation investigates the community structure of web-like networks (i.e., large, random, real-life networks such as the World Wide Web and the Internet). Recently, it has been shown that many such networks have a locally dense and globally sparse structure with certain small, dense subgraphs occurring much more frequently than they do in the classical Erdös-Rényi random graphs. This peculiarity--which is commonly referred to as community structure--has been observed in seemingly unrelated networks such as the Web, email networks, citation networks, biological networks, etc. The pervasiveness of this phenomenon has led many researchers to believe that such cohesive groups of nodes might represent meaningful entities. For example, in the Web such tightly-knit groups of nodes might represent pages with a common topic, geographical location, etc., while in the neural networks they might represent evolved computational units. The notion of community has emerged in an effort to formalize the empirical observation of the locally dense globally sparse structure of web-like networks. In the broadest sense, a community in a web-like network is defined as a group of nodes that induces a dense subgraph which is sparsely linked with the rest of the network. Due to a wide array of envisioned applications, ranging from crawlers and search engines to network security and network compression, there has recently been a widespread interest in finding efficient community-mining algorithms. In this dissertation, the community structure of web-like networks is investigated by a combination of analytical and computational techniques: First, we consider the problem of modeling the web-like networks. In the recent years, many new random graph models have been proposed to account for some recently discovered properties of web-like networks that distinguish them from the classical random graphs. The vast majority of these random graph models take into account only the addition of new nodes and edges. Yet, several empirical observations indicate that deletion of nodes and edges occurs frequently in web-like networks. Inspired by such observations, we propose and analyze two dynamic random graph models that combine node and edge addition with a uniform and a preferential deletion of nodes, respectively. In both cases, we find that the random graphs generated by such models follow power-law degree distributions (in agreement with the degree distribution of many web-like networks). Second, we analyze the expected density of certain small subgraphs--such as defensive alliances on three and four nodes--in various random graphs models. Our findings show that while in the binomial random graph the expected density of such subgraphs is very close to zero, in some dynamic random graph models it is much larger. These findings converge with our results obtained by computing the number of communities in some Web crawls. Next, we investigate the computational complexity of the community-mining problem under various definitions of community. Assuming the definition of community as a global defensive alliance, or a global offensive alliance we prove--using transformations from the dominating set problem--that finding optimal communities is an NP-complete problem. These and other similar complexity results coupled with the fact that many web-like networks are huge, indicate that it is unlikely that fast, exact sequential algorithms for mining communities may be found. To handle this difficulty we adopt an algorithmic definition of community and a simpler version of the community-mining problem, namely: find the largest community to which a given set of seed nodes belong. We propose several greedy algorithms for this problem: The first proposed algorithm starts out with a set of seed nodes--the initial community--and then repeatedly selects some nodes from community's neighborhood and pulls them in the community. In each step, the algorithm uses clustering coefficient--a parameter that measures the fraction of the neighbors of a node that are neighbors themselves--to decide which nodes from the neighborhood should be pulled in the community. This algorithm has time complexity of order , where denotes the number of nodes visited by the algorithm and is the maximum degree encountered. Thus, assuming a power-law degree distribution this algorithm is expected to run in near-linear time. The proposed algorithm achieved good accuracy when tested on some real and computer-generated networks: The fraction of community nodes classified correctly is generally above 80% and often above 90% . A second algorithm based on a generalized clustering coefficient, where not only the first neighborhood is taken into account but also the second, the third, etc., is also proposed. This algorithm achieves a better accuracy than the first one but also runs slower. Finally, a randomized version of the second algorithm which improves the time complexity without affecting the accuracy significantly, is proposed. The main target application of the proposed algorithms is focused crawling--the selective search for web pages that are relevant to a pre-defined topic.
Show less
Date Issued: 2005
Identifier: CFE0000900, ucf:46726
Format: Document (PDF)
PURL: http://purl.flvc.org/ucf/fd/CFE0000900

Title: LEVELS OF LINE GRAPH QUESTION INTERPRETATION WITH INTERMEDIATE ELEMENTARY STUDENTS OF VARYING SCIENTIFIC AND MATHEMATICAL KNOWLEDGE AND ABILITY: A THINK ALOUD STUDY.
Creator: Keller, Stacy, Biraimah, Karen, University of Central Florida
Abstract / Description: This study examined how intermediate elementary students' mathematics and science background knowledge affected their interpretation of line graphs and how their interpretations were affected by graph question levels. A purposive sample of 14 6th-grade students engaged in think aloud interviews (Ericsson & Simon, 1993) while completing an excerpted Test of Graphing in Science (TOGS) (McKenzie & Padilla, 1986). Hand gestures were video recorded. Student performance on the TOGS was assessed...
Show moreThis study examined how intermediate elementary students' mathematics and science background knowledge affected their interpretation of line graphs and how their interpretations were affected by graph question levels. A purposive sample of 14 6th-grade students engaged in think aloud interviews (Ericsson & Simon, 1993) while completing an excerpted Test of Graphing in Science (TOGS) (McKenzie & Padilla, 1986). Hand gestures were video recorded. Student performance on the TOGS was assessed using an assessment rubric created from previously cited factors affecting students' graphing ability. Factors were categorized using Bertin's (1983) three graph question levels. The assessment rubric was validated by Padilla and a veteran mathematics and science teacher. Observational notes were also collected. Data were analyzed using Roth and Bowen's semiotic process of reading graphs (2001). Key findings from this analysis included differences in the use of heuristics, self-generated questions, science knowledge, and self-motivation. Students with higher prior achievement used a greater number and variety of heuristics and more often chose appropriate heuristics. They also monitored their understanding of the question and the adequacy of their strategy and answer by asking themselves questions. Most used their science knowledge spontaneously to check their understanding of the question and the adequacy of their answers. Students with lower and moderate prior achievement favored one heuristic even when it was not useful for answering the question and rarely asked their own questions. In some cases, if students with lower prior achievement had thought about their answers in the context of their science knowledge, they would have been able to recognize their errors. One student with lower prior achievement motivated herself when she thought the questions were too difficult. In addition, students answered the TOGS in one of three ways: as if they were mathematics word problems, science data to be analyzed, or they were confused and had to guess. A second set of findings corroborated how science background knowledge affected graph interpretation: correct science knowledge supported students' reasoning, but it was not necessary to answer any question correctly; correct science knowledge could not compensate for incomplete mathematics knowledge; and incorrect science knowledge often distracted students when they tried to use it while answering a question. Finally, using Roth and Bowen's (2001) two-stage semiotic model of reading graphs, representative vignettes showed emerging patterns from the study. This study added to our understanding of the role of science content knowledge during line graph interpretation, highlighted the importance of heuristics and mathematics procedural knowledge, and documented the importance of perception attentions, motivation, and students' self-generated questions. Recommendations were made for future research in line graph interpretation in mathematics and science education and for improving instruction in this area.
Show less
Date Issued: 2008
Identifier: CFE0002356, ucf:47810
Format: Document (PDF)
PURL: http://purl.flvc.org/ucf/fd/CFE0002356

graph theory (3)	+ -
Gallai-Ramsey number (2)	+ -
kindergarten (2)	+ -
movement (2)	+ -
rainbow triangle (2)	+ -

Academic (1)	+ -
Academic -- Engineering (1)	+ -
ActiGraph (1)	+ -
ActiGraph Link GT9X (1)	+ -
Algorithms (1)	+ -
Attention Deficit Hyperactive Disorder (1)	+ -
Attributed Graph (1)	+ -
BRIEF2 (1)	+ -
Bag of Words (1)	+ -
Bayesian data analysis (1)	+ -
Calculus (1)	+ -
Calculus Reform (1)	+ -
Calculus Tasks (1)	+ -
Cartesian product (1)	+ -
Chronic sleep deprivation (1)	+ -
Cognitive radio networks (1)	+ -
Combinatorics (1)	+ -
Communities (1)	+ -
Commutative Algebra (1)	+ -
Commutativity (1)	+ -
Computer Algebra System (CAS) (1)	+ -
Computer Generated Forces (CGFs) (1)	+ -
Conceptual Understanding (1)	+ -
Concurrent programs (1)	+ -
Context (1)	+ -

ETD Collection (32)	+ -
Honors Collection (2)	+ -

University of Central Florida (33)	+ -
Song, Zixia (8)	+ -
Brennan, Joseph (6)	+ -
Deo, Narsingh (5)	+ -
Zhao, Yue (5)	+ -

Martin, Heath (3)	+ -
Bassiouni, Mostafa (2)	+ -
DeMara, Ronald (2)	+ -
Dutton, Ronald (2)	+ -
Gonzalez, Avelino (2)	+ -
Hughes, Charles (2)	+ -
Mohapatra, Ram (2)	+ -
Reid, Michael (2)	+ -
Song, Zi-Xia (2)	+ -
Abdalla, Ayman Mahmoud (1)	+ -
Allee-Herndon, Karyn (1)	+ -
Balakrishnan, Hemant (1)	+ -
Bawatneh, Zyad (1)	+ -
Biraimah, Karen (1)	+ -
Bosse, Christian (1)	+ -
Brigham, Robert (1)	+ -
Bruce, Dylan (1)	+ -
Burns, Brittany (1)	+ -
Cami, Aurel (1)	+ -
Cheng, Cheng (1)	+ -
Clark, M. H. (1)	+ -
Davenport, Hunter M (1)	+ -
De Vas Gunasekara, Ajani Ruwandhika (1)	+ -
Debnath, Kishore (1)	+ -
Dechev, Damian (1)	+ -

Search In

Pages

Pages

Sort Results By:

Narrow results by:

Topical Subject

Collection

Type of Resource

Language

Creator

Format

Owner