Timeline for Random sample of spanning trees
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 17, 2023 at 6:45 | vote | accept | Paul R | ||
| Nov 16, 2023 at 1:55 | comment | added | David E Speyer | Let $A$ be an array with entries $A[1]$, $A[2]$, ..., $A[n]$, $A[n+1]$. Each element of the array is a pair of integers. Set $L' = L \cup \{ n+1 \}$, which we consider as ordered circularly. If $j \not\in L'$, then $A[j]$ is $(0,0)$. If $j \in L'$, and $i$ and $k$ are the elements of $L'$ before and after $j$, then $A[j] = (i,k)$. Then we can delete $j$ by reading $A[j]$ to find the elements $i$ and $k$ before and after it, and editing $A[i]$, $A[j]$, $A[k]$ appropriately, and we can find the location of the smallest element by looking at $A[n+1]$. | |
| Nov 16, 2023 at 1:51 | comment | added | David E Speyer | So, looking at proofwiki.org/wiki/Labeled_Tree_from_Pr%C3%BCfer_Sequence , it looks like we need a data structure which represents a subset $L$ of $[n]$ such that finding the smallest element, and deleting an arbitrary element from $L$, are both $O(1)$. (This is "the list" in the terminology of the link.) It seems to me that we can do this by combining an array and a doubly linked list, as follows: | |
| Nov 16, 2023 at 0:32 | comment | added | Brendan McKay | @DavidESpeyer I wasn't asking for linear time in the sense of bit complexity and agree that is impossible. I was assuming the model that is used most commonly for combinatorial algorithms, namely that elementary operations with integers of value $O(n)$, i.e. $O(\log n)$ bits, take $O(1)$ time. Otherwise operations like incrementing an array index or accessing an array element would have $O(\log n)$ cost and almost all algorithms advertised as "linear time" would not be. | |
| Nov 15, 2023 at 20:23 | comment | added | David E Speyer | @BrendanMcKay In a very naive computation model, you can't beat $n \log n$ steps because you need $n \log n$ bits of input data to encode all the different trees, and you need to look at all the bits. I imagine you are thinking about some sort of model where you can compare $\log n$ bit integers in $O(1)$ time, but you need to be more careful about specifying your computation model if you want to do something like that. | |
| Nov 15, 2023 at 18:49 | comment | added | David E Speyer | @ManfredWeis Degree sequence does not encode spanning tree. EG there are two isomorphism classes of trees of $10$ vertices with degree sequence $1^6 3^4$: One is the "snowflake" with edges $(0,1)$, $(0,2)$, $(0,3)$, $(1,4)$, $(1,5)$, $(2,6)$, $(2,7)$, $(3,8)$, $(3,9)$; the other is the "caterpillar" with edges $(0,1)$, $(1,2)$, $(2,3)$, $(0,4)$, $(0,5)$, $(1,6)$, $(2,7)$, $(3,8)$, $(3,9)$. | |
| Nov 15, 2023 at 14:05 | comment | added | Brendan McKay | @ManfredWeis Sorting of small integers takes linear time with a bucket sort. | |
| Nov 15, 2023 at 7:27 | comment | added | Manfred Weis | @BrendanMcKay I suspect that a linear algorithm doesn't exist because the algorithm needs to sort vertices according to label values; that seems to be necessary for any unique encoding scheme and thus $O(n \log\, n)$ can't be improved. Would be an interesting question if the degree sequence uniquely encodes trees; that sequence can be calculated in $O(n)$ | |
| Nov 15, 2023 at 0:41 | comment | added | Brendan McKay | Is there a linear time algorithm for turning a Prüfer sequence into a tree? The usual algorithm, for example in Wikipedia, doesn't seem to be linear. I suspect it just needs a better data structure. | |
| Nov 14, 2023 at 19:21 | comment | added | David E Speyer | That said, if you specifically want spanning trees of $K_n$, Prufer codes are probably easier. | |
| Nov 14, 2023 at 19:20 | comment | added | David E Speyer | The random walk can return to earlier vertices: At each step, it goes to a uniformly chosen random neighbor of its current vertex. For each vertex $v$ other then the starting vertex, let $e_v$ be the edge that was traveled right BEFORE the first time that the walk reaches $v$. The set of edges $\{ e_v \}$ turns out to be a spanning tree, chosen uniformly at random. See Aldous cs.cmu.edu/~15859n/RelatedWork/AldousRandomTrees.pdf . | |
| Nov 14, 2023 at 18:38 | comment | added | Jukka Kohonen | Prüfer I understand, but how is the random walk defined? Can the walk go back to already visited vertices? Otherwise I don't understand how it can generate any branching trees. | |
| Nov 14, 2023 at 11:51 | history | answered | Tony Huynh | CC BY-SA 4.0 |