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 9 of 9 for “"subgraph counting"”.

  1. Parameterised algorithms for counting subgraphs, matchings, and monochromatic partitions

    Counting the number of solutions to a computational problem is at least as hard as deciding whether a solution exists. In fact, it is often much harder. However, in theory, as well as in practice, it is often of interest to determine the number of solutions to computational problems. In this …

    glasgow Download PDF for Parameterised algorithms for counting subgraphs, matchings, and monochromatic partitions (opens in a new tab)

  2. Empirical Study of Two Hypothesis Test Methods for Community Structure in Networks

    … which works for dense graph. Another one is the subgraph counting method proposed by Gao and Lafferty (2017a), valid for sparse network. In this paper, firstly, we empirically study the BS or GL methods to see whether either of them works for moderately sparse network; secondly, we propose a …

    ndsu Repository record for Empirical Study of Two Hypothesis Test Methods for Community Structure in Networks (opens in a new tab)

  3. Models of streaming computation

    … tractable. These include: • New algorithms for counting triangles in the insertion-only and linear sketching models, along with tight (up to log factors) lower bounds. • A quantum streaming algorithm for counting triangles, giving the first quantum advantage for a natural one-pass streaming …

    texas Repository record for Models of streaming computation (opens in a new tab)

  4. Monochromatic Subgraphs in Multiplex Networks

    … we study the joint distribution of monochromatic subgraphs for dense multiplex networks, that is, networks with multiple layers. Specifically, given a finite collection of graphs $H_1,\ldots,H_d$, we derive the asymptotic joint distribution of $\bm T_n:= (T(H_1, G_n^{(1)}),\ldots, T(H_d, …

    penn Repository record for Monochromatic Subgraphs in Multiplex Networks (opens in a new tab)

  5. Time Windowed Data Structures

    … problems,window reporting problemsandwindow counting problems.Considering an RE graph G=(|V|=n, |E|=m) as the input, where each edge inEhas a unique positive timestamp, we present data structures to answer the following window problems; (a) decision problems for monotone graph properties, …

    carleton Repository record for Time Windowed Data Structures (opens in a new tab)

  6. Graph analytics and subset selection problems in machine learning

    … relevant to modern machine learning research: 1) Subgraph counting and 2) High-dimensional subset selection. The former can be used to construct features for performing graph analytics. The latter has applications in sparse modeling such as feature selection, sparse regression, and interpretable …

    texas Repository record for Graph analytics and subset selection problems in machine learning (opens in a new tab)

  7. A Study on Privacy Preserving Data Publishing With Differential Privacy

    … private noise over the result of several subgraph queries on a graph dataset. Besides, to ensure expected utility, by selecting a maximal noise level $\theta$, our proposed system can generate noisy result with expected utility. Comparing with existing models for several subgraph counting …

    sask Repository record for A Study on Privacy Preserving Data Publishing With Differential Privacy (opens in a new tab)

  8. Optimal Graph Streaming Algorithms and Further Advances in Modern Models of Computation

    … verification. We begin by studying the 4-cycle counting problem in the fully dynamic model and show an improvement over the previous best algorithm, demonstrating that the previously assumed natural bound was not tight. In the sublinear setting, we examine the problem of estimating matching size …

    waterloo Repository record for Optimal Graph Streaming Algorithms and Further Advances in Modern Models of Computation (opens in a new tab)