Abstract-This paper presenterar en algoritm för att hitta en enkel väg i det givna nätverket med flera måste-include noder i sökvägen. Problemet med att hitta en väg med must-include nod(er) kan lätt hittas i vissa speciella fall. Men i allmänhet, inklusive flera noder i den enkla vägen har visat sig vara NP-Complete. Detta problem kan uppstå i nätområden som att tvinga rutten att gå igenom vissa noder, som har våglängdsomvandlare (optisk), har övervakning (telekom), har gateway-funktioner (i OSPF) eller är basstationer (i MANET). I detta dokument beskrivs en heuristisk algoritm som följer söndra och erövra tillvägagångssätt, genom att dela problemet i två subproblem. Det visas att algoritmen inte växer exponentiellt i detta program och inledande omordning av den givna sekvensen av must-include noder kan förbättra resultatet. De experimentella resultaten visar att algoritmen framgångsrikt beräknar nära optimal väg i rimlig tid.
Begränsa en väg för att vara en enkel väg med flera must-stop noder, utan några ordningskrav, är NP-Complete och i REF, en heuristic föreslås för det.
Finding a simple path with multiple must-include nodes
{'venue': '2009 IEEE International Symposium on Modeling, Analysis & Simulation of Computer and Telecommunication Systems', 'journal': '2009 IEEE International Symposium on Modeling, Analysis & Simulation of Computer and Telecommunication Systems', 'mag_field_of_study': ['Computer Science']}