View All Items

Title: WHEN DOES A GRAPH HAVE A UNIQUE DRAWING ON A SPHERE?.
Creator: FRIEDLANDER, DAVID PAUL, Florida Atlantic University
Abstract/Description: This thesis shows that a planar graph is uniquely embeddable in a sphere whenever it is three-connected and gives related results about planar graphs of lower connectivity and about non- planar graphs. A section on the fourteen non-planar graphs with six vertices is also included.
Date Issued: 1972
PURL: http://purl.flvc.org/fcla/dt/13477
Subject Headings: Graph theory
Format: Document (PDF)

Title: Odd sums of long cycles in 2-connected graphs.
Creator: Teng, Cong., Florida Atlantic University, Locke, Stephen C.
Abstract/Description: Let G be a 2-connected graph with minimum degree d and with at least d + 2 vertices. Suppose that G is not a cycle. Then there is an odd set of cycles, each with length at least d + 1, such that they sum to zero. If G is also non-hamiltonian or bipartite, cycles of length at least 2d can be used.
Date Issued: 1999
PURL: http://purl.flvc.org/fcla/dt/15666
Subject Headings: Paths and cycles (Graph theory), Graph theory
Format: Document (PDF)

Title: Long paths and cycles in graphs with large minimum degree.
Creator: Barovich, Mark V., Florida Atlantic University, Locke, Stephen C.
Abstract/Description: Determining which graphs are hamiltonian is a central unsolved problem in graph theory. More generally, the study of long cycles in graphs has been extensive, and there are numerous results on the subject in the mathematical literature. In this dissertation, we survey several of these results. The study of long paths is related to the study of long cycles. In a graph in which every pair of vertices is connected by a long path, every edge lies on a long cycle. We prove that any set of four...
Show moreDetermining which graphs are hamiltonian is a central unsolved problem in graph theory. More generally, the study of long cycles in graphs has been extensive, and there are numerous results on the subject in the mathematical literature. In this dissertation, we survey several of these results. The study of long paths is related to the study of long cycles. In a graph in which every pair of vertices is connected by a long path, every edge lies on a long cycle. We prove that any set of four vertices lying on a common path in a 2-connected graph lie on a common long path, generalizing a result of Lovasz. We further exploit the relationship between long paths and long cycles to prove that the cycle spaces of a large class of hamiltonian graphs are generated by long cycles, partially proving a conjecture made by Bondy.
Show less
Date Issued: 1998
PURL: http://purl.flvc.org/fcla/dt/12572
Subject Headings: Hamiltonian graph theory
Format: Document (PDF)

Title: THE MINIMUM K-CENTER PROBLEM FOR GRID GRAPH.
Creator: HSUEH, CHI-FU, Florida Atlantic University, Hadlock, Frank O., Hoffman, Frederick, Charles E. Schmidt College of Science, Department of Mathematical Sciences
Abstract/Description: A study was made of the problem of locating M facilities on a connected grid graph, so that M is the minimum and so that every demand node on the graph is within given distance K of one of these M facilities. We call this problem briefly the G(N,K,M) problem, with N denoting the total number of demand nodes. An algorithm for solving this problem by using backtrack technique is presented in this thesis. A heuristic algorithm is also present; although the resulting M is not always minimum, it...
Show moreA study was made of the problem of locating M facilities on a connected grid graph, so that M is the minimum and so that every demand node on the graph is within given distance K of one of these M facilities. We call this problem briefly the G(N,K,M) problem, with N denoting the total number of demand nodes. An algorithm for solving this problem by using backtrack technique is presented in this thesis. A heuristic algorithm is also present; although the resulting M is not always minimum, it tends to be near minimum. The advantage over the backtrack algorithm is that the heuristic algorithm operates very quickly. Algorithms represented in this thesis are programmed in the Pascal language for the Univac 1100 computer at Florida Atlantic University, Boca Raton, Florida.
Show less
Date Issued: 1981
PURL: http://purl.flvc.org/fcla/dt/14077
Subject Headings: Graph theory, Algorithms
Format: Document (PDF)

Title: Some graph connectivity conditions and their implications.
Creator: Abreu, Marien, Florida Atlantic University, Locke, Stephen C.
Abstract/Description: This dissertation studies two independent problems, each related to a special connectivity condition in a simple graph. The first is a distance-degree condition called cohesion. Given a tree T with n vertices, we analyze the minimum integer f(T) = k, in terms of n, for which any connected k-cohesive graph G contains a copy of T, such that G-V(T) is connected. The problem comes from a generalization of an exercise by Lovasz [L7] in which it is shown that f(K2) = 5. Locke, Tracy and Voss [L5]...
Show moreThis dissertation studies two independent problems, each related to a special connectivity condition in a simple graph. The first is a distance-degree condition called cohesion. Given a tree T with n vertices, we analyze the minimum integer f(T) = k, in terms of n, for which any connected k-cohesive graph G contains a copy of T, such that G-V(T) is connected. The problem comes from a generalization of an exercise by Lovasz [L7] in which it is shown that f(K2) = 5. Locke, Tracy and Voss [L5] have proved that in general f(T) > 2n, and in the case in which T is a path, equality is attained. Also Locke [L5.1] proved that f(T) < 4n. Here we improve the upper bound to 4n-6 when T is not a path and to 2n + 2 when T has diameter at most 4. In the particular case of K1,3 we show that f(K1,3) = 2n = 8 is attained. The conjecture that remains open is whether f(T) = 2n for any tree T on n vertices. The second problem studied here is a particular case of the well known relation between the path-connectivity and a set of long cycles, which generate the cycle space of a simple graph. The main conjecture in this topic is by Bondy [B1], and states that if G is a 3-connected graph, with minimum degree at least d and with at least 2d vertices, then every cycle of G can be written as the symmetric difference of an odd number of cycles, each of whose lengths are at least 2d-1. Hartman [H2], Locke [L1, L2, L3], Barovich [BL] and Teng [L6] have proved results related to this conjecture. Here we show that 2-connected, 6-path-connected graphs with at least 9 vertices and minimum degree at least 3 are 6-generated. And more generally, we prove that if a graph G is 2-connected, k-path-connected, and contains a long cycle, then G is (k + 1)-generated, up to some cases which are characterized. The conjecture [L3] of whether, for some constant m, 1/2 < m < 1, every k-path-connected graph is mk-generated, remains open.
Show less
Date Issued: 2003
PURL: http://purl.flvc.org/fcla/dt/12030
Subject Headings: Trees (Graph theory), Paths and cycles (Graph theory)
Format: Document (PDF)

Title: Cycle and path double covers of graphs.
Creator: Wu, Xuegong, Florida Atlantic University, Locke, Stephen C.
Abstract/Description: A cycle double cover (CDC) of a graph G is a collection C of cycles of G such that each edge of G belongs to exactly two members of C. P. D. Seymour conjectured that every 2-edge-connected graph admits a CDC. In a similar way, a path double cover (PDC) of graph G is a collection P of paths of G such that each edge of G belongs to exactly two paths of P. If each vertex of G is an end of exactly two paths of P, then P is called a perfect path double cover (PPDC). J. A. Bondy asked if every...
Show moreA cycle double cover (CDC) of a graph G is a collection C of cycles of G such that each edge of G belongs to exactly two members of C. P. D. Seymour conjectured that every 2-edge-connected graph admits a CDC. In a similar way, a path double cover (PDC) of graph G is a collection P of paths of G such that each edge of G belongs to exactly two paths of P. If each vertex of G is an end of exactly two paths of P, then P is called a perfect path double cover (PPDC). J. A. Bondy asked if every simple graph admits a PPDC. In the first part of this thesis, we present some techniques that have been applied to the cycle double cover conjecture and give a detailed study of CDC for some particular graphs. It has been found that this conjecture is true of planar graphs, 3-edge-colorable cubic graphs, Cayley graphs and graphs which have a Hamiltonian path. In the second part of this thesis, we mainly deal with path double covers and their variants. We will see that every simple graph admits a PPDC and the PPDC problem is in class P. A detailed summary about the main results discussed in this thesis is included.
Show less
Date Issued: 1991
PURL: http://purl.flvc.org/fcla/dt/14687
Subject Headings: Paths and cycles (Graph theory)
Format: Document (PDF)

Title: LONESUM MATRICES AND ACYCLIC ORIENTATIONS: ENUMERATION AND ASYMPTOTICS.
Creator: Khera, Jessica, Lundberg, Erik, Florida Atlantic University, Department of Mathematical Sciences, Charles E. Schmidt College of Science
Abstract/Description: An acyclic orientation of a graph is an assignment of a direction to each edge in a way that does not form any directed cycles. Acyclic orientations of a complete bipartite graph are in bijection with a class of matrices called lonesum matrices, which can be uniquely reconstructed from their row and column sums. We utilize this connection and other properties of lonesum matrices to determine an analytic form of the generating function for the length of the longest path in an acyclic...
Show moreAn acyclic orientation of a graph is an assignment of a direction to each edge in a way that does not form any directed cycles. Acyclic orientations of a complete bipartite graph are in bijection with a class of matrices called lonesum matrices, which can be uniquely reconstructed from their row and column sums. We utilize this connection and other properties of lonesum matrices to determine an analytic form of the generating function for the length of the longest path in an acyclic orientation on a complete bipartite graph, and then study the distribution of the length of the longest path when the acyclic orientation is random. We use methods of analytic combinatorics, including analytic combinatorics in several variables (ACSV), to determine asymptotics for lonesum matrices and other related classes.
Show less
Date Issued: 2021
PURL: http://purl.flvc.org/fau/fd/FA00013716
Subject Headings: Matrices, Combinatorial analysis, Graph theory
Format: Document (PDF)

Title: THE STRUCTURAL ORGANIZATION AND SPECTRAL CHARACTERISTICS OF VISUAL WORKING MEMORY IN THE MONKEY FRONTOPARIETAL NETWORK.
Creator: Conklin, Bryan, Alexander, William, Florida Atlantic University, Center for Complex Systems and Brain Sciences, Charles E. Schmidt College of Science
Abstract/Description: Working memory is a mental workspace which utilizes short and long-term memory to maintain and manipulate information. It is crucial in enabling cognitive control and is largely controlled by interactions within and between frontal and parietal cortices. Recent work has identified visual nonspatial, spatial, and visuospatial working memory spectral characteristics of the local field potential through simultaneous recordings from various areas across the monkey frontoparietal network. However,...
Show moreWorking memory is a mental workspace which utilizes short and long-term memory to maintain and manipulate information. It is crucial in enabling cognitive control and is largely controlled by interactions within and between frontal and parietal cortices. Recent work has identified visual nonspatial, spatial, and visuospatial working memory spectral characteristics of the local field potential through simultaneous recordings from various areas across the monkey frontoparietal network. However, the reports are minimal in number, and there is no clear narrative tying together the heterogenous functionality of the characteristics. Here, a new spectral model of monkey visual working memory is proposed to address these shortcomings. It highlights functional roles for low, mid, and high frequency bands. Next, the organization of structural connectivity which gives rise to these spectral characteristics is investigated. A new binary association matrix representing connections in the frontoparietal network is proposed. A graph theoretic analysis on the matrix found that a 3-node dynamical relaying M9 motif was a fundamental building block of the network. It is optimally structured for the synchrony found in the spectral model. The network was also found to have a small-world architecture, which confers the integration and specialization of function required by visual working memory. Afterwards, three hypotheses generated by the spectral model are tested on non-spatial data. The low and mid band hypotheses were supported by evidence, while the high band hypothesized activity was not observed. This adds credibility to the roles identified in the model for the low and mid band and identifies a need for further investigation of the high band role. Finally, opportunities to expand the spectral model, analyze the M9 motif, and further test the model are explored. In the future, the spectral model could evolve to apply its predictions to humans in the pursuit of treatments for neurological disorders.
Show less
Date Issued: 2020
PURL: http://purl.flvc.org/fau/fd/FA00013584
Subject Headings: Memory, Short-Term, Working memory, Monkeys, Graph theory
Format: Document (PDF)

Title: Graph labeling and non-separating trees.
Creator: Gottipati, Chenchu B., Locke, Stephen C., Florida Atlantic University, Charles E. Schmidt College of Science, Department of Mathematical Sciences
Abstract/Description: This dissertation studies two independent problems, one is about graph labeling and the other problem is related to connectivity condition in a simple graph. Graph labeling is a rapidly developing area of research in graph theory, having connections with a variety of application-oriented areas such as VLSI optimization, data structures and data representation. Furthermore, the connectivity conditions in a simple graphs may help us to study the new aspects of ad hoc networks, social networks...
Show moreThis dissertation studies two independent problems, one is about graph labeling and the other problem is related to connectivity condition in a simple graph. Graph labeling is a rapidly developing area of research in graph theory, having connections with a variety of application-oriented areas such as VLSI optimization, data structures and data representation. Furthermore, the connectivity conditions in a simple graphs may help us to study the new aspects of ad hoc networks, social networks and web graphs. In chapter 2, we study path systems, reduced path systems and how to construct a super edge-graceful tree with any number of edges using path systems. First, we give an algorithm to reduce a labeled path system to a smaller labeled path system of a different type. First, we investigate the cases (m, k) = (3; 5) and (m, k) = (4; 7), where m is the number of paths and 2k is the length of each path, and then we give a generalization for any k, m = 3 and m = 4. We also describe a procedure to construct a super-edge-graceful tree with any number of edges.
Show less
Date Issued: 2014
PURL: http://purl.flvc.org/fau/fd/FA00004289, http://purl.flvc.org/fau/fd/FA00004289
Subject Headings: Computational complexity, Computer graphics, Graph theory, Integrated circuits -- Very large scale integration, Mathematical optimization
Format: Document (PDF)

Title: An Empirical Study of Random Forests for Mining Imbalanced Data.
Creator: Golawala, Moiz M., Khoshgoftaar, Taghi M., Florida Atlantic University
Abstract/Description: Skewed or imbalanced data presents a significant problem for many standard learners which focus on optimizing the overall classification accuracy. When the class distribution is skewed, priority is given to classifying examples from the majority class, at the expense of the often more important minority class. The random forest (RF) classification algorithm, which is a relatively new learner with appealing theoretical properties, has received almost no attention in the context of skewed...
Show moreSkewed or imbalanced data presents a significant problem for many standard learners which focus on optimizing the overall classification accuracy. When the class distribution is skewed, priority is given to classifying examples from the majority class, at the expense of the often more important minority class. The random forest (RF) classification algorithm, which is a relatively new learner with appealing theoretical properties, has received almost no attention in the context of skewed datasets. This work presents a comprehensive suite of experimentation evaluating the effectiveness of random forests for learning from imbalanced data. Reasonable parameter settings (for the Weka implementation) for ensemble size and number of random features selected are determined through experimentation oil 10 datasets. Further, the application of seven different data sampling techniques that are common methods for handling imbalanced data, in conjunction with RF, is also assessed. Finally, RF is benchmarked against 10 other commonly-used machine learning algorithms, and is shown to provide very strong performance. A total of 35 imbalanced datasets are used, and over one million classifiers are constructed in this work.
Show less
Date Issued: 2007
PURL: http://purl.flvc.org/fau/fd/FA00012520
Subject Headings: Data mining--Case studies, Machine learning--Case studies, Data structure (Computer science), Trees (Graph theory)--Case studies
Format: Document (PDF)

Title: Embedding binomial trees in faulty hypercube multiprocessors.
Creator: Luo, Yinqiu., Florida Atlantic University, Wu, Jie, College of Engineering and Computer Science, Department of Computer and Electrical Engineering and Computer Science
Abstract/Description: We study the embedding of binomial trees with variable roots in faulty hypercubes. Based on novel embedding strategies, we propose three embedding algorithms with variable nodes as the root. The first algorithm can tolerate up to n - 1 faulty links, but the execution can be done within log2(n - 1) subcube splits. The second one can tolerate up to [(3(n - 1))\2] faulty links. The last one can tolerate up to [(3(n - 4))\2] faulty nodes.
Date Issued: 1996
PURL: http://purl.flvc.org/fcla/dt/15345
Subject Headings: Hypercube networks (Computer networks), Trees (Graph theory), Multiprocessors, Parallel processing (Electronic computers), Computer algorithms, Fault-tolerant computing, Embedded computer systems
Format: Document (PDF)

Title: Computing topological dynamics from time series.
Creator: Wess, Mark., Charles E. Schmidt College of Science, Department of Mathematical Sciences
Abstract/Description: The topological entropy of a continuous map quantifies the amount of chaos observed in the map. In this dissertation we present computational methods which enable us to compute topological entropy for given time series data generated from a continuous map with a transitive attractor. A triangulation is constructed in order to approximate the attractor and to construct a multivalued map that approximates the dynamics of the linear interpolant on the triangulation. The methods utilize...
Show moreThe topological entropy of a continuous map quantifies the amount of chaos observed in the map. In this dissertation we present computational methods which enable us to compute topological entropy for given time series data generated from a continuous map with a transitive attractor. A triangulation is constructed in order to approximate the attractor and to construct a multivalued map that approximates the dynamics of the linear interpolant on the triangulation. The methods utilize simplicial homology and in particular the Lefschetz Fixed Point Theorem to establish the existence of periodic orbits for the linear interpolant. A semiconjugacy is formed with a subshift of nite type for which the entropy can be calculated and provides a lower bound for the entropy of the linear interpolant. The dissertation concludes with a discussion of possible applications of this analysis to experimental time series.
Show less
Date Issued: 2008
PURL: http://purl.flvc.org/FAU/186294
Subject Headings: Algebraic topology, Graph theory, Fixed point theory, Singularities (Mathematics)
Format: Document (PDF)

Graph theory (7)	+ -
Paths and cycles (Graph theory) (3)	+ -
Trees (Graph theory) (2)	+ -
Algebraic topology (1)	+ -
Algorithms (1)	+ -

Combinatorial analysis (1)	+ -
Computational complexity (1)	+ -
Computer algorithms (1)	+ -
Computer graphics (1)	+ -
Data mining--Case studies (1)	+ -
Data structure (Computer science) (1)	+ -
Embedded computer systems (1)	+ -
Fault-tolerant computing (1)	+ -
Fixed point theory (1)	+ -
Hamiltonian graph theory (1)	+ -
Hypercube networks (Computer networks) (1)	+ -
Integrated circuits -- Very large scale integration (1)	+ -
Machine learning--Case studies (1)	+ -
Mathematical optimization (1)	+ -
Matrices (1)	+ -
Memory, Short-Term (1)	+ -
Monkeys (1)	+ -
Multiprocessors (1)	+ -
Parallel processing (Electronic computers) (1)	+ -
Singularities (Mathematics) (1)	+ -
Trees (Graph theory)--Case studies (1)	+ -
Working memory (1)	+ -

Florida Atlantic University (11)	+ -
Charles E. Schmidt College of Science (5)	+ -
Locke, Stephen C. (5)	+ -
Department of Mathematical Sciences (4)	+ -
Abreu, Marien (1)	+ -

Alexander, William (1)	+ -
Barovich, Mark V. (1)	+ -
Center for Complex Systems and Brain Sciences (1)	+ -
College of Engineering and Computer Science (1)	+ -
Conklin, Bryan (1)	+ -
Department of Computer and Electrical Engineering and Computer Science (1)	+ -
FRIEDLANDER, DAVID PAUL (1)	+ -
Golawala, Moiz M. (1)	+ -
Gottipati, Chenchu B. (1)	+ -
HSUEH, CHI-FU (1)	+ -
Hadlock, Frank O. (1)	+ -
Hoffman, Frederick (1)	+ -
Khera, Jessica (1)	+ -
Khoshgoftaar, Taghi M. (1)	+ -
Lundberg, Erik (1)	+ -
Luo, Yinqiu. (1)	+ -
Teng, Cong. (1)	+ -
Wess, Mark. (1)	+ -
Wu, Jie (1)	+ -
Wu, Xuegong (1)	+ -

Search In

Sort Results By:

Narrow results by:

Collection

Topical Subject

Genre

Type of Resource

Language

Creator

Format

Owner