Vi studerar prospekteringsproblemets beräkningsbarhet och komplexitet i en klass av mycket dynamiska nät: bärargrafer, där kanterna mellan platser endast finns vid några (okända) tidpunkter som definieras av de periodiska förflyttningarna av mobiloperatörer bland webbplatserna. Dessa grafer modellerar naturligtvis mycket dynamiska infrastrukturlösa nät som kollektivtrafik med fasta tidtabeller, satellitsystem med låg omloppsbana (LEO), säkerhetsvakters turer osv. Vi fokuserar på den opportunistiska utforskningen av dessa grafer, det vill säga av en agent som utnyttjar transportörernas rörelser för att flytta in i nätverket. Vi fastställer nödvändiga villkor för att problemet ska kunna lösas. Vi härleder också lägre gränser för den tid som krävs i allmänhet, liksom för de carrier diagram som definieras av begränsade klasser av transportörer rörelser. Vi bevisar sedan att de begränsningar av beräkningsbarheten och komplexiteten som vi har fastställt verkligen är snäva. I själva verket bevisar vi att alla nödvändiga villkor också är tillräckliga och att alla lägre kostnadsbegränsningar är snäva. Vi gör det konstruktivt genom att presentera två optimala lösningsalgoritmer, en för anonyma system, och en för dem med distinkta noder ID.
Det skulle kunna användas för att lösa prospekteringsproblemets beräkningsbarhet och komplexitet i en klass av mycket dynamiska nätverk, som spelade en central roll i DTN:s Ref.
On the Exploration of Time-Varying Networks
{'venue': None, 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}