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 80 for “"sparse graphs"”.

  1. Domination in Sparse Graphs

    Given a partition pi of V (G) with parts ( V1, V2, ... , V t). A pi-dominating set B is a dominating set that is the union of parts of pi. The pi-domination number gamma(G,pi) of G is the size of a smallest pi-dominating set. If each Vi in pi has size at most 2, we call pi a coupling of G and say …

    uiuc Repository record for Domination in Sparse Graphs (opens in a new tab)

  2. Transversal Problems In Sparse Graphs

    … graph $G$ which intersects all copies of subgraphs~$F$ from a fixed family $\mathcal F$. In the first portion of this thesis we show two results related to even cycle transversal. %%Note rephrase this later. In Chapter \ref{ECTChapter}, we present our 47/7-approximation for even cycle …

    waterloo Repository record for Transversal Problems In Sparse Graphs (opens in a new tab)

  3. Resource Allocation on Sparse Graphs

    Considering a network of workers represented by a sparse graph where each worker (ie. node) has a specific load of small independent jobs, our aim is to move the jobs around such that all tasks will be carried out while the communication is minimized. We examine the performance of a new algorithm …

    aston Repository record for Resource Allocation on Sparse Graphs (opens in a new tab) Download PDF for Resource Allocation on Sparse Graphs (opens in a new tab)

  4. Massively parallel algorithms for sparse graphs

    Most real-life graphs are large and sparse, consisting of billions of nodes connected by billions of edges. Single-machine computation for such graphs is often slow and inefficient. The modern approach is to deploy a fleet of machines that work on a given graph problem in parallel. The Massively …

    aalto Repository record for Massively parallel algorithms for sparse graphs (opens in a new tab)

  5. Colorings of sparse graphs and multigraphs

    Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-10-19 without embargo terms

    uiuc Repository record for Colorings of sparse graphs and multigraphs (opens in a new tab)

  6. Safe Semi-Supervised Learning with Sparse Graphs

    There has been substantial interest from both computer science and statistics in developing methods for graph-based semi-supervised learning. The attraction to the area involves several challenging applications brought forth from academia and industry where little data are available with training …

    wvu Repository record for Safe Semi-Supervised Learning with Sparse Graphs (opens in a new tab)

  7. Analytic properties of sparse graphs and hypergraphs

    … Next, we define a class of weighted hypergraphs that satisfy relative counting and removal lemmas. Finally, we present number theoretical and algorithmic applications of the aforementioned results.

    greece Repository record for Analytic properties of sparse graphs and hypergraphs (opens in a new tab)

  8. Accelerating transitive closure of large-scale sparse graphs

    … of real-world systems are typically sparse in nature due to lesser connectivity between nodes. The anti-section approach is designed specifically to improve performance for large scale sparse graphs. The NVIDIA Titan V CPU is used for the execution of the anti-section parallel …

    njit Repository record for Accelerating transitive closure of large-scale sparse graphs (opens in a new tab)

  9. A Faster Breadth-First Search on Sparse Graphs

    … level-synchronous approach works well for dense graphs, where each level is relatively large, but its synchronization requirements limit performance on sparse graphs. Unordered BFS algorithms instead explore graphs without the level constraint, thus removing the synchronization barrier, at the …

    chalmers Repository record for A Faster Breadth-First Search on Sparse Graphs (opens in a new tab)

  10. Algorithms, parallelism and fine-grained complexity for shortest path problems in sparse graphs

    … find a path of minimum weight from s to t. Most graphs that commonly occur in practice are sparse graphs. In this work, we deal with several computational problems related to shortest paths in sparse graphs and we present algorithms that provide significant improvements in performance in both …

    texas Repository record for Algorithms, parallelism and fine-grained complexity for shortest path problems in sparse graphs (opens in a new tab)

  11. Edge colorings of graphs on surfaces and star edge colorings of sparse graphs

    … on two types of edge coloring problems for graphs. For each surface Σ, we define ∆(Σ) = max{∆(G)| G is a class two graph with maximum degree ∆(G) that can be embedded in Σ}. Hence Vizing’s Planar Graph Conjecture can be restated as ∆(Σ) = 5 if Σ is a sphere. For a surface Σ with …

    wvu Repository record for Edge colorings of graphs on surfaces and star edge colorings of sparse graphs (opens in a new tab)

  12. Expander Graphs and Coding Theory

    Expander graphs are highly connected sparse graphs which lie at the interface of many different fields of study. For example, they play important roles in prime sieves, cryptography, compressive sensing, metric embedding, and coding theory to name a few. This thesis focuses on the connections between …

    clemson Repository record for Expander Graphs and Coding Theory (opens in a new tab)

  13. Edge modification on perfect and reducible graphs with application to watermarking

    … to edge modification problems on classes of graphs. For the theoretical part, we study and present polynomial algorithms for the minimum completion problem (i) of a graph with a “tail” for four subclasses of perfect graphs and (ii) of a graph and an added edge for the class of P4-sparse …

    greece Repository record for Edge modification on perfect and reducible graphs with application to watermarking (opens in a new tab)

  14. Quantum information dynamics in many-body systems

    … I study tensor network states defined on generic sparse graphs. Using the intuition that generic graphs are locally tree-like, I develop efficient numerical methods to access local information of such states, which serve as a pathway for studying quantum many-body physics on sparse graphs beyond …

    maryland Repository record for Quantum information dynamics in many-body systems (opens in a new tab)

  15. Development of a branch and price approach involving vertex cloning to solve the maximum weighted independent set problem

    … for standard instances and randomly generated graphs for comparison. We show analytically and computationally that our approach gives tight bounds and it solves both dense and sparse graphs quite quickly.

    tamu Repository record for Development of a branch and price approach involving vertex cloning to solve the maximum weighted independent set problem (opens in a new tab)

  16. Parameterized Approaches for Large-Scale Optimization Problems

    … including: the maximum clique problem in sparse graphs; 0-1 programs with many conflicts; and the node-weighted Steiner tree problem with few terminal nodes. We also study polyhedral counterparts to fixed-parameter tractable algorithms. Specifically, we provide fixed-parameter tractable …

    tamu Repository record for Parameterized Approaches for Large-Scale Optimization Problems (opens in a new tab)

  17. Theory and Applications of Mixed-Integer Fractional Programming

    … combinatorial approach best suitable for sparse graphs. Finally, propose an extension of knapsack problems with fractional objectives arising from applications in service systems design and facility location problems with congestion.

    tamu Repository record for Theory and Applications of Mixed-Integer Fractional Programming (opens in a new tab)

Page 1 of 4