
doi: 10.1137/0214017
A strategy of edge-searching in a graph, useful to subgraph listing problems, is introduced. It gives 4 algorithms (requiring linear space) for listing all triangles and quadrangles in G in O(a(G)m) time (for planar graphs both run in linear time), all subgraphs of order 1 in \(O(\ell a(G)^{\ell -2})\) time and all cliques in O(a(G)m) time per clique (m is the number of edges of G, a(G) its arboricity). Further, an upper bound on a(G) is given: a(G)\(\leq \lceil (2m+n)^{1/2}/2\rceil\), where n is the number of vertices of G.
Graph theory, linear time algorithms, Graph theory (including graph drawing) in computer science, Analysis of algorithms and problem complexity, edge-searching, subgraph listing, quadrangles, cliques, triangles
Graph theory, linear time algorithms, Graph theory (including graph drawing) in computer science, Analysis of algorithms and problem complexity, edge-searching, subgraph listing, quadrangles, cliques, triangles
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 444 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 1% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 0.1% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
