Fetching the paper…
Reading the bibliography…
We consider the problem of counting the number of copies of a fixed graph $H$ within an input graph $G$.
P. Holland and S. Leinhardt, A method for detecting structure in sociometric data. American Journal of Sociology, 76:492-513, 1970
1970
Earlier work this paper cites.
A. Itai and M. Rodeh, Finding a minimum circuit in a graph. SIAM Journal on Computing, 7(4):413-423, 1978
1978
Earlier work this paper cites.
P. Erdős, L. Lovász and J. Spencer, Strong independence of graphcopy functions. Graph Theory and Related Topics, 165-172, 1979.
1979
Earlier work this paper cites.
C. Beeri, R. Fagin, D. Maier, A. Mendelzon, J. Ullman and M. Yannakakis, Properties of acyclic database schemes. In Proceedings of the thirteenth annual ACM symposium on Theory of computing, pp. 355-362, 1981
1981
Earlier work this paper cites.
C. Beeri, R. Fagin, D. Maier and M. Yannakakis, On the desirability of acyclic database schemes. Journal of the ACM (JACM), 30(3), pp. 479-513, 1983
1983
Earlier work this paper cites.
D. W. Matula and L. L. Beck, Smallest-last ordering and clustering and graph coloring algorithms. Journal of the ACM (JACM), 30(3), pp. 417-427, 1983
1983
Earlier work this paper cites.
M. L. Fredman, J. Komlós and E. Szemerédi, Storing a sparse table with O ( 1 ) O(1) worst-case access time. Journal of the ACM (JACM), 31(3), pp. 538-544, 1984
1984
Earlier work this paper cites.
N. Chiba and T. Nishizeki, Arboricity and subgraph listing algorithms. SIAM Journal on computing, 14(1), pp. 210-223, 1985
1985
Earlier work this paper cites.
J. Nešetřil and S. Poljak, On the complexity of the subgraph problem. Commentationes Mathematicae Universitatis Carolinae, 26(2):415-419, 1985
1985
Earlier work this paper cites.
F. R. K. Chung, R. L. Graham and R. M. Wilson, Quasi-random graphs. Combinatorica 9(1989), 345-362
1989
Earlier work this paper cites.
N. Alon, R. Yuster and U. Zwick, Color-coding. Journal of the ACM (JACM), 42(4):844-856, 1995
1995
Earlier work this paper cites.
N. Alon, R. Yuster and U. Zwick, Finding and counting given length cycles. Algorithmica, 17(3):209-223, 1997
1997
Earlier work this paper cites.
A. L. Barabási and R. Albert, Emergence of scaling in random networks. Science, 286(5439), 509-512, 1999.
1999
Earlier work this paper cites.
T. Kloks, D. Kratsch and H. Müller, Finding and counting small induced subgraphs efficiently. Information Processing Letters, 74(3):115-121, 2000
2000
Earlier work this paper cites.
J. H. Van Lint and R. M. Wilson, A course in combinatorics
2001
Earlier work this paper cites.
R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii and U. Alon, Network motifs: simple building blocks of complex networks. Science, 298(5594), 824-827, 2002.
2002
Earlier work this paper cites.
R. Burt, Structural holes and good ideas. American Journal of Sociology, 110(2):349-399, 2004
2004
Earlier work this paper cites.
V. Dalmau and P. Jonsson, The complexity of counting homomorphisms seen from the other side. Theoretical Computer Science, 329(1-3), 315-323, 2004.
2004
Cited alongside, same era.
F. Eisenbrand and F. Grandoni, On the complexity of fixed parameter clique and dominating set, Theoretical Computer Science, 326(1-3):57-67, 2004
2004
Cited alongside, same era.
J. Flum and M. Grohe, The parameterized complexity of counting problems. SIAM Journal on Computing, 33(4), pp. 892-922, 2004
2004
Cited alongside, same era.
N. Przulj, D. G. Corneil and I. Jurisica, Modeling interactome: scale-free or geometric?. Bioinformatics, 20(18):3508-3515, 2004
2004
Cited alongside, same era.
S. Rudich and A. Wigderson, Computational complexity theory
2004
Cited alongside, same era.
A. Abboud and V. Vassilevska Williams, Popular conjectures imply strong lower bounds for dynamic problems. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 434-443
2014
Later among the works it cites.
R. Curticapean and D. Marx, Complexity of counting subgraphs: Only the boundedness of the vertex-cover number counts. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 130-139
2014
Later among the works it cites.
A. E. Sariyuce, C. Seshadhri, A. Pinar and U. V. Catalyurek, Finding the hierarchy of dense subgraphs using nucleus decompositions. In Proceedings, International World Wide Web Conference (WWW), 927-937, 2015
2015
Later among the works it cites.
C. E. Tsourakakis, The k k -clique densest subgraph problem. In Proceedings, International World Wide Web Conference (WWW), 1122-1132, 2015
2015
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
F. Hormozdiari, P. Berenbrink, N. Prulj and S. Cenk Sahinalp, Not all scale-free networks are born equal: The role of the seed graph in PPI network evolution. PLoS Computational Biology, 118, 2007
2007
Cited alongside, same era.
N. Przulj, Biological network comparison using graphlet degree distribution. Bioinformatics, 23(2):177-183, 2007
2007
Cited alongside, same era.
L. Lovász and V. T. Sós, Generalized quasirandom graphs. Journal of Combinatorial Theory, Series B, 98(1), pp. 146-163, 2008
2008
Cited alongside, same era.
A. Björklund, T. Husfeldt, P. Kaski and M. Koivisto, Counting paths and packings in halves. In Proceedings of the 17th Annual European Symposium on Algorithms (ESA), 578-586, 2009
2009
Cited alongside, same era.
V. Vassilevska Williams, Efficient algorithms for clique problems. Information Processing Letters, 109(4):254-257, 2009
2009
Cited alongside, same era.
V. Vassilevska Williams and R. Williams, Finding, minimizing, and counting weighted subgraphs. In Proceedings 41st Annual ACM Symposium on the Theory of Computing, 455-464, 2009
2009
Cited alongside, same era.
A. Khan, N. Li, X. Yan, Z. Guan, S. Chakraborty and S. Tao, Neighborhood based fast graph search in large networks. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of data, 2011
2011
Cited alongside, same era.
A. Benson, D. F. Gleich and J. Leskovec, Higher-order organization of complex networks. Science, 353(6295):163-166, 2016
2016
Later among the works it cites.
J. Brault-Baron, Hypergraph acyclicity revisited. ACM Computing Surveys (CSUR), 49(3), pp. 1-26, 2016
2016
Later among the works it cites.
H. Chen and S. Mengel, Counting answers to existential positive queries: A complexity classification. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pp. 315-326, 2016.
2016
Later among the works it cites.
A. McGregor, S. Vorotnikova and H. T. Vu, Better algorithms for counting triangles in data streams. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pp. 401-411, 2016
2016
Later among the works it cites.
K. Meeks, The challenges of unbounded treewidth in parameterised subgraph counting problems. Discrete Applied Mathematics, 198, 170-194, 2016
2016
Later among the works it cites.
A. Björklund, P. Kaski and Ł. Kowalik, Counting thin subgraphs via packings faster than meet-in-the-middle time. ACM Transactions on Algorithms (TALG), 13(4), 1-26, 2017
2017
Later among the works it cites.
R. Curticapean, H. Dell and D. Marx, Homomorphisms are a good basis for counting small subgraphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 210-223, 2017
2017
Later among the works it cites.
M. Dalirrooyfard, T. D. Vuong and V. Vassilevska Williams, Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 1167-1178, 2019
2019
Later among the works it cites.
S. K. Bera, N. Pashanasangi and C. Seshadhri, Linear Time Subgraph Counting, Graph Degeneracy, and the Chasm at Size Six. In Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), 38:1-38:20
2020
Closest in time.
S. K. Bera, N. Pashanasangi and C. Seshadhri, Near-linear time homomorphism counting in bounded degeneracy graphs: the barrier of long induced cycles. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2315-2332
2021
Closest in time.
M. Bressan, Faster algorithms for counting subgraphs in sparse graphs. Algorithmica, pp. 1-28, 2021
2021
Closest in time.