Current Search: graphing (x)
Pages


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 lineartime algorithm for the creation of arbitrarily large graphs of the discussed class is provided, and a polynomialtime algorithm for recognizing graphs in the class is given. Several invariants for the class are discussed. The edgeface 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 wellknown 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 StackedBook 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 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

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 individualizationrefinement 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 individualizationrefinement 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 representativean approach that performs well in practice. Yet, several families of graphs have been shown to exist which are hard for nautylike algorithms. This dissertation investigates why these graph families pose difficulty for individualizationrefinement 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 individualizationrefinement 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 timethus obviating the only known exponential upperbound on individualizationrefinement 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 guidetree data structure of the preceding technique to use a stronger vertexinvariant, 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 EdgeColorings of Graphs.

Creator

Foster, Austin, Song, Zixia, Reid, Michael, Brennan, Joseph, University of Central Florida

Abstract / Description

A proper edgecoloring of a graph G by positive integers is called an interval edgecoloring 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 edgecolorings 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 edgecolorings to schedule parentteacher conferences so...
Show moreA proper edgecoloring of a graph G by positive integers is called an interval edgecoloring 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 edgecolorings 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 edgecolorings to schedule parentteacher 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 edgecoloring.A wellknown result of Vizing states that for any simple graph $G$, $\chi'(G) \leq \Delta(G) + 1$, where $\chi'(G)$ and $\Delta(G)$ denote the edgechromatic 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 edgecoloring must be of class 1, and thus every graph of class 2 does not have such a coloring.Finding an interval edgecoloring of a given graph is hard. In fact, it has been shown that determining whether a bipartite graph has an interval edgecoloring is NPcomplete. In this thesis, we survey known results on interval edgecolorings 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

GALLAIRAMSEY NUMBERS FOR C7 WITH MULTIPLE COLORS.

Creator

Bruce, Dylan, Song, ZiXia, 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 edgecolorings of complete graphs. For any graphs G, H1, ..., Hk, we write G ? (H1, ..., Hk), or G ? (H)k when H1 = ��� = Hk = H, if every kedgecoloring 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 edgecolorings of complete graphs. For any graphs G, H1, ..., Hk, we write G ? (H1, ..., Hk), or G ? (H)k when H1 = ��� = Hk = H, if every kedgecoloring 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, edgecolorings with no rainbow triangles. From this we define the GallaiRamsey 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 GallaiRamsey 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 graphbased approaches, string graphbased 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 graphbased approaches, string graphbased 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 alphabetsizeindependent 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 graphbased 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 Ktminor 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 K7minor is 7colorable. We begin by showing that every graph with no K_tminor 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 Ktminor 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 K7minor is 7colorable. We begin by showing that every graph with no K_tminor is (2t  6)colorable for t = 7, 8, 9, in the process giving a shorter and computerfree 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 Ktminors is true. Additionally, we show that any graph with no K8?minor is 9colorable, and any graph with no K8?minor is 8colorable. The Kempechain method developed for our proofs of the above results may be of independent interest. We also use Mader's HWege theorem to establish some sufficient conditions for a graph to contain a K8minor.Another motivation for my research is a wellknown conjecture of Erd?s and Lov(&)#225;sz from 1968, the DoubleCritical Graph Conjecture. A connected graph G is doublecritical if for all edges xy ? E(G), ?(G  x  y) = ?(G)  2. Erd?s and Lov(&)#225;sz conjectured that the only doublecritical tchromatic 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 noncomplete, doublecritical, tchromatic graph contains Kt as a minor for t ? 8. We give a shorter proof of this result for t = 7, a computerfree proof for t = 8, and extend the result to show that G contains a K9minor for all t ? 9. Finally, we show that the DoubleCritical Graph Conjecture is true for doublecritical graphs with chromatic number t ? 8 if such graphs are clawfree.
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 diameterconstrained 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 diameterconstrained minimum spanning tree (DCMST) of a given undirected, edgeweighted graph, G, is the smallestweight 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 NPcomplete 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 diameterconstrained minimum spanning tree (DCMST) of a given undirected, edgeweighted graph, G, is the smallestweight 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 NPcomplete for all values of k; 4 <= k <= (n  2), except when all edgeweights 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 datastructure, 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 RAMSEYMINIMAL GRAPHS.

Creator

Davenport, Hunter M, Song, ZiXia, 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 edgecolorings of complete graphs. For forbidden graphs H1,...,Hk and a graph G, we write G "arrows" (H1,...,Hk) if every kedgecoloring of G contains a monochromatic copy of Hi in color i for some i=1,2,...,k. If c is a (red, blue)edgecoloring 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 edgecolorings of complete graphs. For forbidden graphs H1,...,Hk and a graph G, we write G "arrows" (H1,...,Hk) if every kedgecoloring of G contains a monochromatic copy of Hi in color i for some i=1,2,...,k. If c is a (red, blue)edgecoloring 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)Ramseyminimal 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 Fsaturated 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 objectoriented languages such as Java. This formalism is called sparse because, in contrast to other OO and Javaspecific 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 objectoriented languages such as Java. This formalism is called sparse because, in contrast to other OO and Javaspecific adaptations of PDG's, it introduces few node types and no new edge types beyond those used in traditional dependencebased 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 Javalike 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 componentbased 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 componentbased 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 preexplanation and a postexplanation. The preexplanation is intended to help the user understand the decision making process. The postexplanation 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 realworld 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 realworld situations, additional considerations are important. In particular, since each vertex in a defensive alliance represents some realworld 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 statechart 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 runtime statechart 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 nonblocking 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 runtime statechart 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 nonblocking 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 runtime execution of concurrent program and representing object states in all possible thread interleavings as states and transitions. Using statechart 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 nondeterministic 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 stateofthe 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 realworld random networks like the WWW, Internet, social networks, citation networks, etc., organize themselves into closelyknit groups that are locally dense and globally sparse. These closelyknit 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 realworld random networks like the WWW, Internet, social networks, citation networks, etc., organize themselves into closelyknit groups that are locally dense and globally sparse. These closelyknit 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 communitydiscovery 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 communitydiscovery algorithms is their computational complexity. These algorithms do not scale up to the enormous size of the realworld networks. We propose a hashtablebased 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 fiveyear period. Our results show superlinear 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 QUERYBYCONCEPT.

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 lowlevel features such as colors and textures. The latter model allows queries to be expressed in the form of highlevel 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 lowlevel features such as colors and textures. The latter model allows queries to be expressed in the form of highlevel 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 semanticgap between them. This research involves finding the best method that maps a set of lowlevel features into highlevel 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 lowlevel features and predetermined highlevel 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 offline. This difference allows QBC techniques to shift the timeconsuming 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 Samplingbased Image Annotation) is a technique based on a new samplingbased 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 highperformance 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 WEBLIKE NETWORKS: MODELS AND ALGORITHMS.

Creator

Cami, Aurel, Deo, Narsingh, University of Central Florida

Abstract / Description

This dissertation investigates the community structure of weblike networks (i.e., large, random, reallife 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ösRényi random graphs. This peculiaritywhich is commonly referred to as community structurehas been observed in...
Show moreThis dissertation investigates the community structure of weblike networks (i.e., large, random, reallife 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ösRényi random graphs. This peculiaritywhich is commonly referred to as community structurehas 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 tightlyknit 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 weblike networks. In the broadest sense, a community in a weblike 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 communitymining algorithms. In this dissertation, the community structure of weblike networks is investigated by a combination of analytical and computational techniques: First, we consider the problem of modeling the weblike networks. In the recent years, many new random graph models have been proposed to account for some recently discovered properties of weblike 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 weblike 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 powerlaw degree distributions (in agreement with the degree distribution of many weblike networks). Second, we analyze the expected density of certain small subgraphssuch as defensive alliances on three and four nodesin 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 communitymining problem under various definitions of community. Assuming the definition of community as a global defensive alliance, or a global offensive alliance we proveusing transformations from the dominating set problemthat finding optimal communities is an NPcomplete problem. These and other similar complexity results coupled with the fact that many weblike 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 communitymining 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 nodesthe initial communityand then repeatedly selects some nodes from community's neighborhood and pulls them in the community. In each step, the algorithm uses clustering coefficienta parameter that measures the fraction of the neighbors of a node that are neighbors themselvesto 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 powerlaw degree distribution this algorithm is expected to run in nearlinear time. The proposed algorithm achieved good accuracy when tested on some real and computergenerated 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 crawlingthe selective search for web pages that are relevant to a predefined 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 6thgrade 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 6thgrade 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, selfgenerated questions, science knowledge, and selfmotivation. 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) twostage 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' selfgenerated 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
Pages