Name
Abstract | ||
|---|---|---|
Motivated by the discovery of combinatorial patterns in an undirected graph G with n vertices and m edges, we study the problem of listing all the trees with k vertices that are subgraphs of G. We present the first optimal output-sensitive algorithm, i.e. runs in O(sk) time where s is the number of these trees in G, and uses O(m) space. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/978-3-642-23719-5_24 | ESA |
Keywords | Field | DocType |
n vertex,optimal output-sensitive algorithm,k vertex,output-sensitive listing,undirected graph,combinatorial pattern,bounded-size tree,m edge | Discrete mathematics,Graph,Trémaux tree,Combinatorics,Tree (graph theory),Vertex (geometry),Level structure,Enumeration,Mathematics,Bounded function | Conference |
Volume | ISSN | Citations |
6942 | 0302-9743 | 8 |
PageRank | References | Authors |
0.64 | 5 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Rui Ferreira | 1 | 37 | 4.95 |
| Roberto Grossi | 2 | 607 | 27.03 |
| Romeo Rizzi | 3 | 895 | 100.75 |