Timeline for Ways to paint a backbone on a tree
Current License: CC BY-SA 4.0
23 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 20, 2024 at 21:16 | comment | added | emanresu A | @CursorCoercer addd | |
| Aug 20, 2024 at 21:12 | history | edited | emanresu A | CC BY-SA 4.0 | added 194 characters in body |
| Aug 20, 2024 at 20:52 | comment | added | CursorCoercer | Suggested testcase [[1,2],[1,3],[2,4],[2,5],[3,6],[3,7],[4,8],[4,9],[5,10],[5,11],[6,12],[6,13],[7,14],[7,15]] with 3 backbones | |
| Aug 20, 2024 at 20:19 | answer | added | CursorCoercer | timeline score: 5 | |
| Aug 19, 2024 at 12:26 | comment | added | Antares | @pigrammer: Okay, that is clear to me, but why not only keep the longest path and discarding all shorter ones is not. But this maybe is just something specific to the task. | |
| Aug 19, 2024 at 11:18 | comment | added | pigrammer | @Antares because the graph is a tree there is only one path between any two vertices. | |
| Aug 19, 2024 at 6:21 | comment | added | Antares | Shouldn't the term backbone have a constraint like "being the longest possible path" between two terminal vertices? And also, why is a backbone considered same up to rearrangement? That makes sense only if all the nodes are identical in their properties (which they are here as a special case because they are not defined having any properties at all). -- Just some thoughts, not that I know of any official definition of such a term. | |
| Aug 18, 2024 at 12:09 | answer | added | 138 Aspen | timeline score: 1 | |
| Aug 18, 2024 at 4:37 | comment | added | Simd | @quarague Tree isomorphism can be solved in linear time. Graph isomorphism is in fact not NP hard but there is no provably fast algorithm currently. | |
| Aug 18, 2024 at 0:00 | comment | added | quarague | Doesn't this require some checks for graph isomorphism which in general is NP-hard? Or is graph isomorphism for trees much easier? | |
| Aug 17, 2024 at 12:43 | answer | added | Neil | timeline score: 5 | |
| Aug 17, 2024 at 4:47 | answer | added | Mukundan314 | timeline score: 13 | |
| Aug 16, 2024 at 19:57 | comment | added | emanresu A | @Mukundan314 a) Sure b) added | |
| Aug 16, 2024 at 19:57 | history | became hot network question | |||
| Aug 16, 2024 at 19:56 | history | edited | emanresu A | CC BY-SA 4.0 | added 163 characters in body |
| Aug 16, 2024 at 18:17 | comment | added | Mukundan314 | Suggested testcase: [[1, 2], [2, 3], [2, 4], [4, 5], [4, 6], [6, 7], [7, 8], [7, 9]] this has five backbones. This breaks solutions which try to check isomorphism of two paths by only comparing number of nodes connected to each node on the path. | |
| Aug 16, 2024 at 16:51 | comment | added | Mukundan314 | Can we take the input as a adjacency list? | |
| Aug 16, 2024 at 15:48 | comment | added | CursorCoercer | @l4m2 Indeed all backbones will be uniquely defined by a pair of leaves and vice versa. For any backbone it must contain two and only two leaves, the start and end of the path, and for any two leaves there must be at least one backbone which starts and ends on them since the tree is connected, and there cannot be more than one, as then the graph would contain a loop and thus not be a tree. | |
| Aug 16, 2024 at 14:51 | answer | added | Ajax1234 | timeline score: 2 | |
| Aug 16, 2024 at 11:21 | comment | added | l4m2 | Same isomorphism requirement picking leaves | |
| Aug 16, 2024 at 9:29 | comment | added | emanresu A | @l4m2 No, because of the isomorphism requirement - if you have e.g. the graph with one central node and three nodes attached to it there's only one distinct backbone | |
| Aug 16, 2024 at 9:04 | comment | added | l4m2 | Is it equal to "pick two leaves"? | |
| Aug 16, 2024 at 8:59 | history | asked | emanresu A | CC BY-SA 4.0 |