Timeline for Does there exist a linear-time algorithm to find a basis of the null space of the adjacency matrix of a tree?
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 3, 2016 at 16:01 | comment | added | Federico Poloni | Not necessarily -- aelguindy showed an example in which the basis is composed of $\approx n$ vectors, but in that specific case they can be encoded as a set of sparse vectors using linear space. So we don't have a counterexample for now, but we are considering the possibility that there might be one. | |
| Nov 3, 2016 at 15:38 | comment | added | Daniel Alejandro Jaume | Complexity is not my thing. Are you telling my that any algorithm must be at least quadratic? | |
| Nov 3, 2016 at 15:30 | comment | added | Daniel Alejandro Jaume | First: lineal on |V(T)|, the number of vertices of the tree. | |
| Nov 3, 2016 at 15:09 | comment | added | aelguindy | Indeed, a star graph has nullity (n - 2), so (at least a naive) encoding of the output has ~ $n^2$ numbers. | |
| Nov 3, 2016 at 14:54 | history | edited | Federico Poloni | CC BY-SA 3.0 |
edited title
|
| Nov 3, 2016 at 14:53 | comment | added | Federico Poloni | At first glance, it's not even clear to me if the output has always at most linear size. | |
| Nov 3, 2016 at 14:34 | history | edited | Daniel Alejandro Jaume | CC BY-SA 3.0 |
edited title
|
| Nov 3, 2016 at 12:10 | history | edited | Chris Godsil |
Added tag
|
|
| Nov 3, 2016 at 10:56 | history | asked | Daniel Alejandro Jaume | CC BY-SA 3.0 |