Current Search: Trees Graph theory (x)
View All Items
 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 distancedegree 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 kcohesive graph G contains a copy of T, such that GV(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 distancedegree 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 kcohesive graph G contains a copy of T, such that GV(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 4n6 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 pathconnectivity 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 3connected 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 2d1. Hartman [H2], Locke [L1, L2, L3], Barovich [BL] and Teng [L6] have proved results related to this conjecture. Here we show that 2connected, 6pathconnected graphs with at least 9 vertices and minimum degree at least 3 are 6generated. And more generally, we prove that if a graph G is 2connected, kpathconnected, 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 kpathconnected graph is mkgenerated, 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
 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 commonlyused 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 miningCase studies, Machine learningCase 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, Faulttolerant computing, Embedded computer systems
 Format
 Document (PDF)