I den här artikeln tar vi upp problemet med att söka i kant efter vägda träd. Det visas att det finns en polynom-tid algoritm för att hitta optimal ansluten sökstrategi för avgränsade grad träd med godtyckliga vikter på kanterna och hörn av trädet. Problemet är NP-komplett för allmänna nodviktade träd (vikten för varje kant är 1).
I REF är det också bevisat att den viktade edge-searching är NP-komplett på träd och att det finns ett polynom på träd med begränsad grad.
Connected searching of weighted trees
{'venue': 'Theoretical Computer Science 412 (2011) 5700-5713', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}