Documents
Presentation Slides
Presentation Slides
Speeding up compact planar graphs by using shallower trees
- Citation Author(s):
- Submitted by:
- Alexander Irribarra
- Last updated:
- 4 March 2022 - 7:12pm
- Document Type:
- Presentation Slides
- Document Year:
- 2022
- Event:
- Categories:
Comments
Construction Heuristics
It is interesting to see that different spanning trees give rise to different practical performances in terms of the query times.
Do you know whether the observed time bounds can be proven theoretically, e.g.., whether DFS_primal is always the worst case,
or do you think that this observation depends on your graph instance?
Further, I would like to ask whether you can think that you can optimize your spanning tree for a set of vertices that are given by the user at construction time. The idea would be that the user already knows the vertices he/she will frequently query, and asks for the construction achieving the fastest queries.
Hello Dominik, thank you for
Hello Dominik, thank you for your questions.
Regarding the first question, we are not sure if the bounds can be proven theoretically. I do think that the topology of the graph itself also has a big importance, for example, if your graph is already a tree, the only variable you can control is the root that you choose.
Regarding the second question, that is indeed a follow up idea that we have discussed for this work. If we already know the vertices that will be frequently queried, it would be desirable to have as most of its neighbors as posible as leaves, since that reduces the distance between their parentheses. We have not still implemented and tested that, but it is something that is taken into account.
Hello Alexander! Thanks for
Hello Alexander! Thanks for your answers. Maybe the second question can be answered by a greedy approach, prioritizing the connection of the selected nodes while constructing the spanning tree.