Abstrakt. T. Parsons föreslog ursprungligen och studerade följande jaktevasionsproblem på grafer: Medlemmar i ett team av sökare korsar kanterna på en graf G i jakten på en rymling, som rör sig längs grafens kanter med fullständig kunskap om förföljarnas platser. Vad är det minsta antalet s(G) sökare som kommer att räcka för att garantera fånga av rymlingen? Det visas att avgöra om s(G) 5 K, för ett givet heltal K, är NP-komplett för allmänna grafer men kan lösas i linjär tid för träd. Vi ger också en strukturell karakterisering av dessa grafer G med s(G)zzKforK= 1,2,3.
Megiddo m.fl. REF, bevisade att beslutsversionen av problemet är NP-fullständig i allmänhet och lösbar i linjär tid på träd.
The complexity of searching a graph
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}