Log in

Relevant bibliographies by topics / Subgraph Counting / Journal articles

Journal articles on the topic 'Subgraph Counting'

To see the other types of publications on this topic, follow the link: Subgraph Counting.

Author: Grafiati

Published: 10 December 2022

Last updated: 28 January 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Subgraph Counting.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Ribeiro, Pedro, Pedro Paredes, Miguel E. P. Silva, David Aparicio, and Fernando Silva. "A Survey on Subgraph Counting." ACM Computing Surveys 54, no. 2 (April 2021): 1–36. http://dx.doi.org/10.1145/3433652.

Full text

Abstract:

Computing subgraph frequencies is a fundamental task that lies at the core of several network analysis methodologies, such as network motifs and graphlet-based metrics, which have been widely used to categorize and compare networks from multiple domains. Counting subgraphs is, however, computationally very expensive, and there has been a large body of work on efficient algorithms and strategies to make subgraph counting feasible for larger subgraphs and networks. This survey aims precisely to provide a comprehensive overview of the existing methods for subgraph counting. Our main contribution is a general and structured review of existing algorithms, classifying them on a set of key characteristics, highlighting their main similarities and differences. We identify and describe the main conceptual approaches, giving insight on their advantages and limitations, and we provide pointers to existing implementations. We initially focus on exact sequential algorithms, but we also do a thorough survey on approximate methodologies (with a trade-off between accuracy and execution time) and parallel strategies (that need to deal with an unbalanced search space).

APA, Harvard, Vancouver, ISO, and other styles

2

Zhang, Hao, Jeffrey Xu Yu, Yikai Zhang, Kangfei Zhao, and Hong Cheng. "Distributed subgraph counting." Proceedings of the VLDB Endowment 13, no. 12 (August 2020): 2493–507. http://dx.doi.org/10.14778/3407790.3407840.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Sze, Lawrence. "The number of edges on generalizations of Paley graphs." International Journal of Mathematics and Mathematical Sciences 27, no. 2 (2001): 111–23. http://dx.doi.org/10.1155/s0161171201002071.

Full text

Abstract:

Evans, Pulham, and Sheenan computed the number of complete4-subgraphs of Paley graphs by counting the number of edges of the subgraph containing only those nodesxfor whichxandx−1are quadratic residues. Here we obtain formulae for the number of edges of generalizations of these subgraphs using Gaussian hypergeometric series and elliptic curves. Such formulae are simple in several infinite families, including those studied by Evans, Pulham, and Sheenan.

APA, Harvard, Vancouver, ISO, and other styles

4

FÜRER, MARTIN, and SHIVA PRASAD KASIVISWANATHAN. "Approximately Counting Embeddings into Random Graphs." Combinatorics, Probability and Computing 23, no. 6 (July 9, 2014): 1028–56. http://dx.doi.org/10.1017/s0963548314000339.

Full text

Abstract:

LetHbe a graph, and letCH(G) be the number of (subgraph isomorphic) copies ofHcontained in a graphG. We investigate the fundamental problem of estimatingCH(G). Previous results cover only a few specific instances of this general problem, for example the case whenHhas degree at most one (the monomer-dimer problem). In this paper we present the first general subcase of the subgraph isomorphism counting problem, which is almost always efficiently approximable. The results rely on a new graph decomposition technique. Informally, the decomposition is a labelling of the vertices such that every edge is between vertices with different labels, and for every vertex all neighbours with a higher label have identical labels. The labelling implicitly generates a sequence of bipartite graphs, which permits us to break the problem of counting embeddings of large subgraphs into that of counting embeddings of small subgraphs. Using this method, we present a simple randomized algorithm for the counting problem. For all decomposable graphsHand all graphsG, the algorithm is an unbiased estimator. Furthermore, for all graphsHhaving a decomposition where each of the bipartite graphs generated is small and almost all graphsG, the algorithm is a fully polynomial randomized approximation scheme.We show that the graph classes ofHfor which we obtain a fully polynomial randomized approximation scheme for almost allGincludes graphs of degree at most two, bounded-degree forests, bounded-width grid graphs, subdivision of bounded-degree graphs, and major subclasses of outerplanar graphs, series-parallel graphs and planar graphs of large girth, whereas unbounded-width grid graphs are excluded. Moreover, our general technique can easily be applied to proving many more similar results.

APA, Harvard, Vancouver, ISO, and other styles

5

McKay, Brendan D., and Stanisław P. Radziszowski. "Subgraph Counting Identities and Ramsey Numbers." Journal of Combinatorial Theory, Series B 69, no. 2 (March 1997): 193–209. http://dx.doi.org/10.1006/jctb.1996.1741.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Roth, Marc. "Parameterized Counting of Partially Injective Homomorphisms." Algorithmica 83, no. 6 (March 11, 2021): 1829–60. http://dx.doi.org/10.1007/s00453-021-00805-y.

Full text

Abstract:

AbstractWe study the parameterized complexity of the problem of counting graph homomorphisms with given partial injectivity constraints, i.e., inequalities between pairs of vertices, which subsumes counting of graph homomorphisms, subgraph counting and, more generally, counting of answers to equi-join queries with inequalities. Our main result presents an exhaustive complexity classification for the problem in fixed-parameter tractable and $$\#\mathsf {W[1]}$$ # W [ 1 ] -complete cases. The proof relies on the framework of linear combinations of homomorphisms as independently discovered by Chen and Mengel (PODS 16) and by Curticapean, Dell and Marx in the recent breakthrough result regarding the exact complexity of the subgraph counting problem (STOC 17). Moreover, we invoke Rota’s NBC-Theorem to obtain an explicit criterion for fixed-parameter tractability based on treewidth. The abstract classification theorem is then applied to the problem of counting locally injective graph homomorphisms from small pattern graphs to large target graphs. As a consequence, we are able to fully classify its parameterized complexity depending on the class of allowed pattern graphs.

APA, Harvard, Vancouver, ISO, and other styles

7

Bressan, Marco. "Faster algorithms for counting subgraphs in sparse graphs." Algorithmica 83, no. 8 (February 22, 2021): 2578–605. http://dx.doi.org/10.1007/s00453-021-00811-0.

Full text

Abstract:

AbstractGiven a k-node pattern graph H and an n-node host graph G, the subgraph counting problem asks to compute the number of copies of H in G. In this work we address the following question: can we count the copies of H faster if G is sparse? We answer in the affirmative by introducing a novel tree-like decomposition for directed acyclic graphs, inspired by the classic tree decomposition for undirected graphs. This decomposition gives a dynamic program for counting the homomorphisms of H in G by exploiting the degeneracy of G, which allows us to beat the state-of-the-art subgraph counting algorithms when G is sparse enough. For example, we can count the induced copies of any k-node pattern H in time $$2^{O(k^2)} O(n^{0.25k + 2} \log n)$$ 2 O ( k 2 ) O ( n 0.25 k + 2 log n ) if G has bounded degeneracy, and in time $$2^{O(k^2)} O(n^{0.625k + 2} \log n)$$ 2 O ( k 2 ) O ( n 0.625 k + 2 log n ) if G has bounded average degree. These bounds are instantiations of a more general result, parameterized by the degeneracy of G and the structure of H, which generalizes classic bounds on counting cliques and complete bipartite graphs. We also give lower bounds based on the Exponential Time Hypothesis, showing that our results are actually a characterization of the complexity of subgraph counting in bounded-degeneracy graphs.

APA, Harvard, Vancouver, ISO, and other styles

8

Liu, Xin, and Yangqiu Song. "Graph Convolutional Networks with Dual Message Passing for Subgraph Isomorphism Counting and Matching." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 7 (June 28, 2022): 7594–602. http://dx.doi.org/10.1609/aaai.v36i7.20725.

Full text

Abstract:

Graph neural networks (GNNs) and message passing neural networks (MPNNs) have been proven to be expressive for subgraph structures in many applications. Some applications in heterogeneous graphs require explicit edge modeling, such as subgraph isomorphism counting and matching. However, existing message passing mechanisms are not designed well in theory. In this paper, we start from a particular edge-to-vertex transform and exploit the isomorphism property in the edge-to-vertex dual graphs. We prove that searching isomorphisms on the original graph is equivalent to searching on its dual graph. Based on this observation, we propose dual message passing neural networks (DMPNNs) to enhance the substructure representation learning in an asynchronous way for subgraph isomorphism counting and matching as well as unsupervised node classification. Extensive experiments demonstrate the robust performance of DMPNNs by combining both node and edge representation learning in synthetic and real heterogeneous graphs.

APA, Harvard, Vancouver, ISO, and other styles

9

Che, Yulin, Zhuohang Lai, Shixuan Sun, Yue Wang, and Qiong Luo. "Accelerating truss decomposition on heterogeneous processors." Proceedings of the VLDB Endowment 13, no. 10 (June 2020): 1751–64. http://dx.doi.org/10.14778/3401960.3401971.

Full text

Abstract:

Truss decomposition is to divide a graph into a hierarchy of subgraphs, or trusses. A subgraph is a k -truss ( k ≥ 2) if each edge is in at least k --- 2 triangles in the subgraph. Existing algorithms work by first counting the number of triangles each edge is in and then iteratively incrementing k to peel off the edges that will not appear in ( k + 1)-truss. Due to the data and computation intensity, truss decomposition on billion-edge graphs takes hours to complete on a commodity computer. We propose to accelerate in-memory truss decomposition by (1) compacting intermediate results to optimize memory access, (2) dynamically adjusting the computation based on data characteristics, and (3) parallelizing the algorithm on both the multicore CPU and the GPU. In particular, we optimize the triangle enumeration with data skew handling, and determine at runtime whether to pursue peeling or direct triangle counting to obtain a certain k -truss. We further develop a CPU-GPU co-processing strategy in which the CPU first computes intermediate results and sends the compacted results to the GPU for further computation. Our experiments on real-world datasets show that our implementations outperform the state of the art by up to an order of magnitude. Our source code is publicly available at https://github.com/RapidsAtHKUST/AccTrussDecomposition.

APA, Harvard, Vancouver, ISO, and other styles

10

WANLESS, IAN M. "Counting Matchings and Tree-Like Walks in Regular Graphs." Combinatorics, Probability and Computing 19, no. 3 (February 10, 2010): 463–80. http://dx.doi.org/10.1017/s0963548309990678.

Full text

Abstract:

The number of closed tree-like walks in a graph is closely related to the moments of the roots of the matching polynomial for the graph. Thus, by counting these walks up to a given length it is possible to find approximations for the matching polynomial. This approach has been used in two separate problems involving asymptotic enumerations of 1-factorizations of regular graphs. Nevertheless, a systematic way to count the required walks had not previously been found.In this paper we give an algorithm to count closed tree-like walks in a regular graph up to a given length. For smallm, this provides expressions for the number ofm-matchings in the graph in terms of the numbers of copies of certain small subgraphs that appear in the graph. The simplest of these expressions were already known, having been rediscovered by numerous authors usingad hocmethods. We offer the first general method for producing the expressions. We also find generating functions that isolate the contribution from the simplest kind of subgraph – namely a single cycle of arbitrary length.

APA, Harvard, Vancouver, ISO, and other styles

11

Wang, Yuyi, Jan Ramon, and Thomas Fannes. "An efficiently computable subgraph pattern support measure: counting independent observations." Data Mining and Knowledge Discovery 27, no. 3 (May 9, 2013): 444–77. http://dx.doi.org/10.1007/s10618-013-0318-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

Brešar, Boštjan, Wilfried Imrich, and Sandi Klavžar. "Reconstructing subgraph-counting graph polynomials of increasing families of graphs." Discrete Mathematics 297, no. 1-3 (July 2005): 159–66. http://dx.doi.org/10.1016/j.disc.2005.02.019.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Gerbner, Dániel, and Cory Palmer. "Counting copies of a fixed subgraph in F-free graphs." European Journal of Combinatorics 82 (December 2019): 103001. http://dx.doi.org/10.1016/j.ejc.2019.103001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Meeks, Kitty. "The challenges of unbounded treewidth in parameterised subgraph counting problems." Discrete Applied Mathematics 198 (January 2016): 170–94. http://dx.doi.org/10.1016/j.dam.2015.06.019.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

Yang, Jianye, Yun Peng, and Wenjie Zhang. "(p,q)-biclique counting and enumeration for large sparse bipartite graphs." Proceedings of the VLDB Endowment 15, no. 2 (October 2021): 141–53. http://dx.doi.org/10.14778/3489496.3489497.

Full text

Abstract:

In this paper, we study the problem of ( p , q)-biclique counting and enumeration for large sparse bipartite graphs. Given a bipartite G = ( U, V , E), and two integer parameters p and q, we aim to efficiently count and enumerate all (p, q)-bicliques in G , where a (p, q)-biclique B ( L, R ) is a complete subgraph of G with L ⊆ U, R ⊆ V , |L| = p, and |R| = q. The problem of (p, q)-biclique counting and enumeration has many applications, such as graph neural network information aggregation, densest subgraph detection, and cohesive subgroup analysis, etc. Despite the wide range of applications, to the best of our knowledge, we note that there is no efficient and scalable solution to this problem in the literature. This problem is computationally challenging, due to the worst-case exponential number of (p, q)-bicliques. In this paper, we propose a competitive branch-and-bound baseline method, namely BCList, which explores the search space in a depth-first manner, together with a variety of pruning techniques. Although BCList offers a useful computation framework to our problem, its worst-case time complexity is exponential to p + q. To alleviate this, we propose an advanced approach, called BCList++. Particularly, BCList++ applies a layer based exploring strategy to enumerate ( p, q )-bicliques by anchoring the search on either U or V only, which has a worst-case time complexity exponential to either p or q only. Consequently, a vital task is to choose a layer with the least computation cost. To this end, we develop a cost model, which is built upon an unbiased estimator for the density of 2-hop graph induced by U or V. To improve computation efficiency, BCList++ exploits pre-allocated arrays and vertex labeling techniques such that the frequent subgraph creating operations can be substituted by array element switching operations. We conduct extensive experiments on 16 real-life datasets, and the experimental results demonstrate that BCList++ significantly outperforms the baseline methods by up to 3 orders of magnitude. We show via a case study that (p, q)-bicliques optimize the efficiency of graph neural networks.

APA, Harvard, Vancouver, ISO, and other styles

16

Focke, Jacob, Leslie Ann Goldberg, and Stanislav Živný. "The Complexity of Approximately Counting Retractions to Square-free Graphs." ACM Transactions on Algorithms 17, no. 3 (August 2021): 1–51. http://dx.doi.org/10.1145/3458040.

Full text

Abstract:

A retraction is a homomorphism from a graph G to an induced subgraph H of G that is the identity on H . In a long line of research, retractions have been studied under various algorithmic settings. Recently, the problem of approximately counting retractions was considered. We give a complete trichotomy for the complexity of approximately counting retractions to all square-free graphs (graphs that do not contain a cycle of length 4). It turns out there is a rich and interesting class of graphs for which this problem is complete in the class #BIS. As retractions generalise homomorphisms, our easiness results extend to the important problem of approximately counting homomorphisms. By giving new #BIS-easiness results, we now settle the complexity of approximately counting homomorphisms for a whole class of non-trivial graphs that were previously unresolved.

APA, Harvard, Vancouver, ISO, and other styles

17

Jin, Wei, Fangyue Chen, and Qinbin He. "Directed Projection Graph of N-Dimensional Hypercube and Subhypercube Decomposition of Balanced Linearly Separable Boolean Functions." International Journal of Bifurcation and Chaos 31, no. 09 (July 2021): 2150138. http://dx.doi.org/10.1142/s0218127421501388.

Full text

Abstract:

A directed projection graph of the [Formula: see text]-dimensional hypercube on the two-dimensional plane is successfully created. Any [Formula: see text]-variable Boolean function can be easily transformed to an induced subgraph of the projection. Therefore, the discussions on [Formula: see text]-variable Boolean functions only need to focus on a two-dimensional planar graph. Some mathematical theories on the projection graph and the induced subgraph are established, and some properties and characteristics of a balanced linearly separable Boolean function (BLSBF) are uncovered. In particular, the sub-hypercube decompositions of BLSBF is easily represented on the projection, and meanwhile, the enumeration scheme for counting the number of [Formula: see text]-variable BLSBFs is developed by using equivalence classification and conformal transformation. With the aid of the directed projection grap constructed in this paper, one can further study many difficult problems in some fields such as Boolean functions and artificial neural networks.

APA, Harvard, Vancouver, ISO, and other styles

18

Privault, Nicolas, and Grzegorz Serafin. "Normal approximation for sums of weighted $U$-statistics – application to Kolmogorov bounds in random subgraph counting." Bernoulli 26, no. 1 (February 2020): 587–615. http://dx.doi.org/10.3150/19-bej1141.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

Tutaj, Edward. "Prime numbers with a certain extremal type property." Annales Universitatis Paedagogicae Cracoviensis. Studia Mathematica 17, no. 1 (December 1, 2018): 127–51. http://dx.doi.org/10.2478/aupcsm-2018-0010.

Full text

Abstract:

Abstract The convex hull of the subgraph of the prime counting function x → π(x) is a convex set, bounded from above by a graph of some piecewise affine function x → (x). The vertices of this function form an infinite sequence of points $({e_k},\pi ({e_k}))_1^\infty $ . The elements of the sequence (ek)1∞ shall be called the extremal prime numbers. In this paper we present some observations about the sequence (ek)1∞ and we formulate a number of questions inspired by the numerical data. We prove also two – it seems – interesting results. First states that if the Riemann Hypothesis is true, then ${{{e_k} + 1} \over {{e_k}}} = 1$ . The second, also depending on Riemann Hypothesis, describes the order of magnitude of the differences between consecutive extremal prime numbers.

APA, Harvard, Vancouver, ISO, and other styles

20

STARK, DUDLEY, and NICK WORMALD. "The Probability of Non-Existence of a Subgraph in a Moderately Sparse Random Graph." Combinatorics, Probability and Computing 27, no. 4 (May 9, 2018): 672–715. http://dx.doi.org/10.1017/s0963548318000202.

Full text

Abstract:

We develop a general procedure that finds recursions for statistics counting isomorphic copies of a graph G0 in the common random graph models ${\cal G}$(n,m) and ${\cal G}$(n,p). Our results apply when the average degrees of the random graphs are below the threshold at which each edge is included in a copy of G0. This extends an argument given earlier by the second author for G0=K3 with a more restricted range of average degree. For all strictly balanced subgraphs G0, our results give much information on the distribution of the number of copies of G0 that are not in large ‘clusters’ of copies. The probability that a random graph in ${\cal G}$(n,p) has no copies of G0 is shown to be given asymptotically by the exponential of a power series in n and p, over a fairly wide range of p. A corresponding result is also given for ${\cal G}$(n,m), which gives an asymptotic formula for the number of graphs with n vertices, m edges and no copies of G0, for the applicable range of m. An example is given, computing the asymptotic probability that a random graph has no triangles for p=o(n−7/11) in ${\cal G}$(n,p) and for m=o(n15/11) in ${\cal G}$(n,m), extending results of the second author.

APA, Harvard, Vancouver, ISO, and other styles

21

Chang, Yi-Jun, Seth Pettie, Thatchaphol Saranurak, and Hengjie Zhang. "Near-optimal Distributed Triangle Enumeration via Expander Decompositions." Journal of the ACM 68, no. 3 (May 13, 2021): 1–36. http://dx.doi.org/10.1145/3446330.

Full text

Abstract:

We present improved distributed algorithms for variants of the triangle finding problem in the model. We show that triangle detection, counting, and enumeration can be solved in rounds using expander decompositions . This matches the triangle enumeration lower bound of by Izumi and Le Gall [PODC’17] and Pandurangan, Robinson, and Scquizzato [SPAA’18], which holds even in the model. The previous upper bounds for triangle detection and enumeration in were and , respectively, due to Izumi and Le Gall [PODC’17]. An -expander decomposition of a graph is a clustering of the vertices such that (i) each cluster induces a subgraph with conductance at least and (ii) the number of inter-cluster edges is at most . We show that an -expander decomposition with can be constructed in rounds for any and positive integer . For example, a -expander decomposition only requires rounds to compute, which is optimal up to subpolynomial factors, and a -expander decomposition can be computed in rounds, for any arbitrarily small constant . Our triangle finding algorithms are based on the following generic framework using expander decompositions, which is of independent interest. We first construct an expander decomposition. For each cluster, we simulate algorithms with small overhead by applying the expander routing algorithm due to Ghaffari, Kuhn, and Su [PODC’17] Finally, we deal with inter-cluster edges using recursive calls.

APA, Harvard, Vancouver, ISO, and other styles

22

Amini, Omid, Fedor V. Fomin, and Saket Saurabh. "Counting Subgraphs via Homomorphisms." SIAM Journal on Discrete Mathematics 26, no. 2 (January 2012): 695–717. http://dx.doi.org/10.1137/100789403.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Williams, Virginia Vassilevska, and Ryan Williams. "Finding, Minimizing, and Counting Weighted Subgraphs." SIAM Journal on Computing 42, no. 3 (January 2013): 831–54. http://dx.doi.org/10.1137/09076619x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Borbényi, Márton, and Péter Csikvári. "Counting degree-constrained subgraphs and orientations." Discrete Mathematics 343, no. 6 (June 2020): 111842. http://dx.doi.org/10.1016/j.disc.2020.111842.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

CALEGARI, Danny, and Koji FUJIWARA. "Counting subgraphs in hyperbolic graphs with symmetry." Journal of the Mathematical Society of Japan 67, no. 3 (July 2015): 1213–26. http://dx.doi.org/10.2969/jmsj/06731213.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Kowaluk, Mirosław, Andrzej Lingas, and Eva-Marta Lundell. "Counting and Detecting Small Subgraphs via Equations." SIAM Journal on Discrete Mathematics 27, no. 2 (January 2013): 892–909. http://dx.doi.org/10.1137/110859798.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Kloks, Ton, Dieter Kratsch, and Haiko Müller. "Finding and counting small induced subgraphs efficiently." Information Processing Letters 74, no. 3-4 (May 2000): 115–21. http://dx.doi.org/10.1016/s0020-0190(00)00047-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

Fomin, Fedor V., Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh, and B. V. Raghavendra Rao. "Faster algorithms for finding and counting subgraphs." Journal of Computer and System Sciences 78, no. 3 (May 2012): 698–706. http://dx.doi.org/10.1016/j.jcss.2011.10.001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Tahaei, Maedeh S., and Seyed Naser Hashemi. "Graph Characterization by Counting Sink Star Subgraphs." Journal of Mathematical Imaging and Vision 57, no. 3 (October 8, 2016): 439–54. http://dx.doi.org/10.1007/s10851-016-0686-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Ozsvárt, László. "Counting ordered graphs that avoid certain subgraphs." Discrete Mathematics 339, no. 7 (July 2016): 1871–77. http://dx.doi.org/10.1016/j.disc.2016.01.007.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Zhao, Zhao, Langshi Chen, Mihai Avram, Meng Li, Guanying Wang, Ali Butt, Maleq Khan, Madhav Marathe, Judy Qiu, and Anil Vullikanti. "Finding and Counting Tree-Like Subgraphs Using MapReduce." IEEE Transactions on Multi-Scale Computing Systems 4, no. 3 (July 1, 2018): 217–30. http://dx.doi.org/10.1109/tmscs.2017.2768426.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

Rödl, Vojtĕch, and Jozef Skokan. "Counting subgraphs in quasi-random 4-uniform hypergraphs." Random Structures & Algorithms 26, no. 1-2 (January 2005): 160–203. http://dx.doi.org/10.1002/rsa.20056.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Gonen, Mira, Dana Ron, and Yuval Shavitt. "Counting Stars and Other Small Subgraphs in Sublinear-Time." SIAM Journal on Discrete Mathematics 25, no. 3 (January 2011): 1365–411. http://dx.doi.org/10.1137/100783066.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Efthymiou, Charilaos. "Deterministic counting of graph colourings using sequences of subgraphs." Combinatorics, Probability and Computing 29, no. 4 (June 22, 2020): 555–86. http://dx.doi.org/10.1017/s0963548320000255.

Full text

Abstract:

AbstractIn this paper we propose a polynomial-time deterministic algorithm for approximately counting the k-colourings of the random graph G(n, d/n), for constant d>0. In particular, our algorithm computes in polynomial time a $(1\pm n^{-\Omega(1)})$ -approximation of the so-called ‘free energy’ of the k-colourings of G(n, d/n), for $k\geq (1+\varepsilon) d$ with probability $1-o(1)$ over the graph instances.Our algorithm uses spatial correlation decay to compute numerically estimates of marginals of the Gibbs distribution. Spatial correlation decay has been used in different counting schemes for deterministic counting. So far algorithms have exploited a certain kind of set-to-point correlation decay, e.g. the so-called Gibbs uniqueness. Here we deviate from this setting and exploit a point-to-point correlation decay. The spatial mixing requirement is that for a pair of vertices the correlation between their corresponding configurations becomes weaker with their distance.Furthermore, our approach generalizes in that it allows us to compute the Gibbs marginals for small sets of nearby vertices. Also, we establish a connection between the fluctuations of the number of colourings of G(n, d/n) and the fluctuations of the number of short cycles and edges in the graph.

APA, Harvard, Vancouver, ISO, and other styles

35

Dörfler, Julian, Marc Roth, Johannes Schmitt, and Philip Wellnitz. "Counting Induced Subgraphs: An Algebraic Approach to #W[1]-Hardness." Algorithmica 84, no. 2 (December 7, 2021): 379–404. http://dx.doi.org/10.1007/s00453-021-00894-9.

Full text

Abstract:

AbstractWe study the problem $$\#\textsc {IndSub}(\varPhi )$$ # I N D S U B ( Φ ) of counting all induced subgraphs of size k in a graph G that satisfy the property $$\varPhi $$ Φ . It is shown that, given any graph property $$\varPhi $$ Φ that distinguishes independent sets from bicliques, $$\#\textsc {IndSub}(\varPhi )$$ # I N D S U B ( Φ ) is hard for the class $$\#\mathsf {W[1]}$$ # W [ 1 ] , i.e., the parameterized counting equivalent of $${{\mathsf {N}}}{{\mathsf {P}}}$$ N P . Under additional suitable density conditions on $$\varPhi $$ Φ , satisfied e.g. by non-trivial monotone properties on bipartite graphs, we strengthen $$\#\mathsf {W[1]}$$ # W [ 1 ] -hardness by establishing that $$\#\textsc {IndSub}(\varPhi )$$ # I N D S U B ( Φ ) cannot be solved in time $$f(k)\cdot n^{o(k)}$$ f ( k ) · n o ( k ) for any computable function f, unless the Exponential Time Hypothesis fails. Finally, we observe that our results remain true even if the input graph G is restricted to be bipartite and counting is done modulo a fixed prime.

APA, Harvard, Vancouver, ISO, and other styles

36

FARR, G. E. "The Complexity of Counting Colourings of Subgraphs of the Grid." Combinatorics, Probability and Computing 15, no. 03 (April 7, 2006): 377. http://dx.doi.org/10.1017/s0963548305007364.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Jerrum, Mark, and Kitty Meeks. "The parameterised complexity of counting even and odd induced subgraphs." Combinatorica 37, no. 5 (October 24, 2016): 965–90. http://dx.doi.org/10.1007/s00493-016-3338-5.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Bondy, J. A. "Counting subgraphs a new approach to the Caccetta-Häggkvist conjecture." Discrete Mathematics 165-166 (March 1997): 71–80. http://dx.doi.org/10.1016/s0012-365x(96)00162-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Aliakbarpour, Maryam, Amartya Shankha Biswas, Themis Gouleakis, John Peebles, Ronitt Rubinfeld, and Anak Yodpinyanee. "Sublinear-Time Algorithms for Counting Star Subgraphs via Edge Sampling." Algorithmica 80, no. 2 (February 10, 2017): 668–97. http://dx.doi.org/10.1007/s00453-017-0287-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

40

Roth, Marc, and Johannes Schmitt. "Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness." Algorithmica 82, no. 8 (January 22, 2020): 2267–91. http://dx.doi.org/10.1007/s00453-020-00676-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

Jerrum, Mark, and Kitty Meeks. "The parameterised complexity of counting connected subgraphs and graph motifs." Journal of Computer and System Sciences 81, no. 4 (June 2015): 702–16. http://dx.doi.org/10.1016/j.jcss.2014.11.015.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

Alazemi, Abdullah, Milica Andjelic, and Slobodan Simic. "On the spectral invariants of symmetric matrices with applications in the spectral graph theory." Filomat 31, no. 10 (2017): 2925–32. http://dx.doi.org/10.2298/fil1710925a.

Full text

Abstract:

We first prove a formula which relates the characteristic polynomial of a matrix (or of a weighted graph), and some invariants obtained from its principal submatrices (resp. vertex deleted subgraphs). Consequently, we express the spectral radius of the observed objects in the form of power series. In particular, as is relevant for the spectral graph theory, we reveal the relationship between spectral radius of a simple graph and its combinatorial structure by counting certain walks in any of its vertex deleted subgraphs. Some computational results are also included in the paper.

APA, Harvard, Vancouver, ISO, and other styles

43

Gam, A. V. "Comparison the effectiveness two methods: of the spanning trees sampling method and method Rand-ESU." Journal of Physics: Conference Series 2182, no. 1 (March 1, 2022): 012019. http://dx.doi.org/10.1088/1742-6596/2182/1/012019.

Full text

Abstract:

Abstract Calculation of the cutoff probability in the Rand-ESU method. Identification of weak points of the method through the random sampling of spanning trees, also the Rand-ESU method with has implemented in the igraph library. Implemented in library igraph. Comparison of methods for counting subgraphs at four vertices. Prospects for the development of the spanning tree sampling method.

APA, Harvard, Vancouver, ISO, and other styles

44

Björklund, Andreas, Petteri Kaski, and Łukasz Kowalik. "Counting Thin Subgraphs via Packings Faster than Meet-in-the-Middle Time." ACM Transactions on Algorithms 13, no. 4 (December 21, 2017): 1–26. http://dx.doi.org/10.1145/3125500.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

Fowler, Patrick W., Barry T. Pickup, and Tsanka Z. Todorova. "A graph-theoretical model for ballistic conduction in single-molecule conductors." Pure and Applied Chemistry 83, no. 8 (April 27, 2011): 1515–28. http://dx.doi.org/10.1351/pac-con-10-10-16.

Full text

Abstract:

The tight-binding version of the source-and-sink potential (SSP) model of ballistic conduction can be cast in a graph-theoretical form where the transmission through a molecular wire depends on four characteristic polynomials: those of the molecular graph and the vertex-deleted subgraphs with one or both of the molecular vertices contacting the electrodes removed. This gives an explicit function for the dependence of transmission on energy, one that is well adapted for qualitative description of general classes of conductors and conduction behavior. It also leads directly to a selection-rule criterion for conduction in terms of counting zero roots of the polynomials, which for benzenoids and graphenes is shown to subsume literature approaches based on Kekulé structure counting, bond order, and frontier-orbital matching. As explicitly demonstrated here, the SSP transmission function agrees with that derived by the Green’s function (GF) method.

APA, Harvard, Vancouver, ISO, and other styles

46

Liśkiewicz, Maciej, Mitsunori Ogihara, and Seinosuke Toda. "The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes." Theoretical Computer Science 304, no. 1-3 (July 2003): 129–56. http://dx.doi.org/10.1016/s0304-3975(03)00080-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Bressan, Marco, Stefano Leucci, and Alessandro Panconesi. "Faster Motif Counting via Succinct Color Coding and Adaptive Sampling." ACM Transactions on Knowledge Discovery from Data 15, no. 6 (May 19, 2021): 1–27. http://dx.doi.org/10.1145/3447397.

Full text

Abstract:

We address the problem of computing the distribution of induced connected subgraphs, aka graphlets or motifs , in large graphs. The current state-of-the-art algorithms estimate the motif counts via uniform sampling by leveraging the color coding technique by Alon, Yuster, and Zwick. In this work, we extend the applicability of this approach by introducing a set of algorithmic optimizations and techniques that reduce the running time and space usage of color coding and improve the accuracy of the counts. To this end, we first show how to optimize color coding to efficiently build a compact table of a representative subsample of all graphlets in the input graph. For 8-node motifs, we can build such a table in one hour for a graph with 65M nodes and 1.8B edges, which is times larger than the state of the art. We then introduce a novel adaptive sampling scheme that breaks the “additive error barrier” of uniform sampling, guaranteeing multiplicative approximations instead of just additive ones. This allows us to count not only the most frequent motifs, but also extremely rare ones. For instance, on one graph we accurately count nearly 10.000 distinct 8-node motifs whose relative frequency is so small that uniform sampling would literally take centuries to find them. Our results show that color coding is still the most promising approach to scalable motif counting.

APA, Harvard, Vancouver, ISO, and other styles

48

Karoński, Michał, and Andrzej Ruciński. "Poisson convergence and semi-induced properties of random graphs." Mathematical Proceedings of the Cambridge Philosophical Society 101, no. 2 (March 1987): 291–300. http://dx.doi.org/10.1017/s0305004100066664.

Full text

Abstract:

Barbour [l] invented an ingenious method of establishing the asymptotic distribution of the number X of specified subgraphs of a random graph. The novelty of his method relies on using the first two moments of X only, despite the traditional method of moments that involves all moments of X (compare [8, 10, 11, 14]). He also adjusted that new method for counting isolated trees of a given size in a random graph. (For further applications of Barbour's method see [4] and [10].) The main goal of this paper is to show how this method can be extended to a general setting that enables us to derive asymptotic distributions of subsets of vertices of a random graph with various properties.

APA, Harvard, Vancouver, ISO, and other styles

49

Mokhlissi, Raihana, Dounia Lotfi, Joyati Debnath, Mohamed El Marraki, and Noussaima EL Khattabi. "The Evaluation of the Number and the Entropy of Spanning Trees on Generalized Small-World Networks." Journal of Applied Mathematics 2018 (September 3, 2018): 1–7. http://dx.doi.org/10.1155/2018/1017308.

Full text

Abstract:

Spanning trees have been widely investigated in many aspects of mathematics: theoretical computer science, combinatorics, so on. An important issue is to compute the number of these spanning trees. This number remains a challenge, particularly for large and complex networks. As a model of complex networks, we study two families of generalized small-world networks, namely, the Small-World Exponential and the Koch networks, by changing the size and the dimension of the cyclic subgraphs. We introduce their construction and their structural properties which are built in an iterative way. We propose a decomposition method for counting their number of spanning trees and we obtain the exact formulas, which are then verified by numerical simulations. From this number, we find their spanning tree entropy, which is lower than that of the other networks having the same average degree. This entropy allows quantifying the robustness of the networks and characterizing their structures.

APA, Harvard, Vancouver, ISO, and other styles

50

Karimov, E. M. "THE ROLE OF INTRAZONAL FEATURES IN CLARIFYING THE ROAD AND CLIMATIC ZONING OF THE TERRITORY OF SOUTHWESTERN KYRGYZSTAN." Herald of KSUCTA n a N Isanov, no. 2-2-2022 (April 30, 2022): 574–82. http://dx.doi.org/10.35803/1694-5298.2022.2.574-582.

Full text

Abstract:

In mountainous areas, the water-thermal regime of the road bed largely depends on the terrain, in relatively short sections, natural conditions can change - microrelief and microclimate. Therefore, when designing and erecting a subgrade, general standard solutions must be specified in the order of detailed design, depending on natural conditions, including the properties of the soil. Counting for geographical complexes in the design and construction of roads is decided on the basis of road-climatic zoning of territories. Intrazonality is one of the components of the geographical complex in mountainous areas. The study of intrazonal signs in the zoning of roads in the territory of southwestern Kyrgyzstan will greatly help in dividing and clarifying the boundaries of climatic zones of roads.

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!