Global ETD Search

Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.

Results

Showing 1 to 20 of 131 for “"Independent sets"”.

  1. Independent sets and closed-shell independent sets of fullerenes

    … to finding a graph-theoretical maximum independent set: a vertex subset of maximum size such that no two vertices are adjacent. The problem of determining the maximum independent set order is NP-hard for general cubic planar graphs and the complexity for the fullerene subclass was …

    uvic Repository record for Independent sets and closed-shell independent sets of fullerenes (opens in a new tab)

  2. Independent Sets and Eigenspaces

    … that each can be reduced to characterizing the independent sets of maximum size in a suitable graph. A second common feature is that the size of these independent sets meets an eigenvalue bound due to Delsarte and Hoffman. Thirdly, the graphs that arise belong to association schemes that have …

    waterloo Repository record for Independent Sets and Eigenspaces (opens in a new tab)

  3. Independent sets in (r, s)-trees

    Thesis (Ph. D.)--Michigan State University. Department of Mathematics, 1992

    msu Repository record for Independent sets in (r, s)-trees (opens in a new tab)

  4. Independent sets in graph products via harmonic analysis

    In this thesis we study the independent sets of Knr , the weak product of n complete graphs on r vertices, which are close to be of maximum size. We review the previously known results. For constant r and arbitrary n, it was known that every such independent set is close to some independent set of …

    concordia Download PDF for Independent sets in graph products via harmonic analysis (opens in a new tab)

  5. Independent Sets in Some Classical Groups of Dimension Three

    Given a finite group G, an independent set S in G is a set where no element of S can be written as a word in the other elements of S. A minimax set is an independent generating set for G of largest size in G. This thesis seeks to find a good upper bound for the size of minimax sets in SL(3,q) for …

    birmingham Download PDF for Independent Sets in Some Classical Groups of Dimension Three (opens in a new tab)

  6. Extremal results for the number of matchings and independent sets

    … Chapter 5, we answer an extremal question about independent sets in hypergraphs. In a graph G = (V,E), a set A ⊆ V is independent if ∥A ∩ e∥< 2 for all e ∈ E. The graph with n vertices and e edges achieving the maximum number of independent sets is the colex graph. In a hypergraph H = (V,E), a …

    nebraska Repository record for Extremal results for the number of matchings and independent sets (opens in a new tab)

  7. On Maximum Weight Independent Sets and the Set Partitioning Problem

    Made available in DSpace on 2014-12-14T13:09:44Z (GMT). No. of bitstreams: 1 8009103.pdf: 2080632 bytes, checksum: 8b27f27acb1dd7e80416171889173a3d (MD5) Previous issue date: 1979

    uiuc Repository record for On Maximum Weight Independent Sets and the Set Partitioning Problem (opens in a new tab)

  8. Bluetooth scatternet formation protocol for wireless devices based on maximal independent sets

    … protocol called BlueMis that is based on maximal independent set and guarantees connectivity and degree limitation. Three variations of the protocol are introduced with the basic idea of selecting slaves as the maximal independent set of each Bluetooth device. First, BlueMis as a simple unique …

    ottawa-retro Repository record for Bluetooth scatternet formation protocol for wireless devices based on maximal independent sets (opens in a new tab)

  9. Extremal problems on edge-colorings, independent sets, and cycle spectra of graphs

    … graph theory with respect to edge-colorings, independent sets, and cycle spectra. In Chapters 2 and 3, we present results in Ramsey theory, where we seek Ramsey host graphs with small maximum degree. In Chapter 4, we study a Ramsey-type problem on edge-labeled trees, where we seek subtrees …

    uiuc Repository record for Extremal problems on edge-colorings, independent sets, and cycle spectra of graphs (opens in a new tab)

  10. KE Theory & the Number of Vertices Belonging to All Maximum Independent Sets in a Graph

    … let $\alpha (G)$ be the cardinality of a maximum independent set, let $\mu (G)$ be the cardinality of a maximum matching and let $\xi (G)$ be the number of vertices belonging to all maximum independent sets. Boros, Golumbic and Levit showed that in connected graphs where the independence number …

    vcu Repository record for KE Theory & the Number of Vertices Belonging to All Maximum Independent Sets in a Graph (opens in a new tab)

  11. Sub-optimality of Local Algorithms on Sparse Random Graphs

    … important structures on large graphs such as independent sets, matchings, colourings and eigenfunctions of the graph Laplacian with only constant running time and little memory usage. Hatami, Lovasz and Szegedy conjectured that all reasonable optimization problems on large random d-regular …

    toronto-retro Repository record for Sub-optimality of Local Algorithms on Sparse Random Graphs (opens in a new tab)

  12. DVR-Matroids of Algebraic Extensions

    … is a finite set E along with a collection of subsets of E, called independent sets, that satisfy certain conditions. The most well-known matroids are linear matroids, which come from a finite subset of a vector space over a field K. In this case the independent sets are the subsets that are …

    utk-theses Repository record for DVR-Matroids of Algebraic Extensions (opens in a new tab)

  13. Efficient Setup Algorithms for Parallel Algebraic Multigrid

    … itself. A new algorithm labeled Bucket Sorted Independent Sets (BSIS) is developed and contributes two major advances. First, the cost of selecting independent sets while coarsening is substantially less expensive, with experiments demonstrating 23% savings over CLJP-c. Second, theory is …

    uiuc Repository record for Efficient Setup Algorithms for Parallel Algebraic Multigrid (opens in a new tab)

  14. Directed acyclic constrained connectivity: complexity and applications

    … can be related to the enumeration of Maximal Independent Sets. This means that some cases of Directed Acyclic Constrained Connectivity are solvable in polynomial time using advanced algorithms for enumerating Maximal Independent Sets. Finally, we apply our findings to a problem in the field of …

    colostate Repository record for Directed acyclic constrained connectivity: complexity and applications (opens in a new tab)

  15. Homogeneous sets in graphs and hypergraphs

    … or a hypergraph is called homogeneous if it is independent, that is it does not contain any edge, or if it is complete, that is it contains all possible pairs or subsets of it as edges. We investigate the properties of graphs and hypergraphs in two cases of imposed restrictions on the structure …

    oxford Repository record for Homogeneous sets in graphs and hypergraphs (opens in a new tab)

  16. INDEPENDENCE NUMBER OF SPECIFIED I-GRAPHS

    … Petersen Graphs. We provide constructions of independent sets given any parameters, as well as bounds for some subclasses of I-graphs. We also prove exact results for some specific I-graphs.

    nps Repository record for INDEPENDENCE NUMBER OF SPECIFIED I-GRAPHS (opens in a new tab)

  17. Independence Polynomials of Molecular Graphs

    … certain molecules were related to the number of independent vertex sets in the molecular graphs of those chemicals. This led to the definition of the Merrifield-Simmons index of a graph G as the number of independent vertex sets in G. This parameter was extended by graph theorists, who counted …

    mississippi Repository record for Independence Polynomials of Molecular Graphs (opens in a new tab)

Page 1 of 7