Name
Abstract | ||
|---|---|---|
We show that the maximum number of different square substrings in unrooted labelled trees behaves much differently than in words. A substring in a tree corresponds (as its value) to a simple path. Let $\textsf{sq}(n)$ be the maximum number of different square substrings in a tree of size n. We show that asymptotically $\textsf{sq}(n)$ is strictly between linear and quadratic orders, for some constants c1,c20 we obtain: $$c_1n^{4/3} \le \textsf{sq}(n) \le c_2n^{4/3}.$$ |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-31265-6_3 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
quadratic order,unrooted labelled tree,size n,tree corresponds,maximum number,simple path,different square substrings,constants c1 | Discrete mathematics,Combinatorics,Substring,Path (graph theory),Quadratic equation,Mathematics | Conference |
Citations | PageRank | References |
7 | 0.54 | 9 |
Authors | ||
8 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maxime Crochemore | 1 | 2655 | 281.75 |
| Costas S. Iliopoulos | 2 | 1534 | 167.43 |
| Tomasz Kociumaka | 3 | 217 | 38.57 |
| Marcin Kubica | 4 | 629 | 29.26 |
| Jakub Radoszewski | 5 | 624 | 50.36 |
| Wojciech Rytter | 6 | 2290 | 181.52 |
| Wojciech Tyczyński | 7 | 9 | 0.92 |
| Tomasz Waleń | 8 | 706 | 39.62 |