Current Search:  Trees Graph theory (x)

View All Items

  • CSV Spreadsheet
(1 - 3 of 3)
Some graph connectivity conditions and their implications
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)
An Empirical Study of Random Forests for Mining Imbalanced Data
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)
Embedding binomial trees in faulty hypercube multiprocessors
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)