Vi betraktar tidsgrafer med diskreta tidsetiketter och undersöker storleken och ungefärligheten av minsta tidsuppkopplade spännviddsdelgrafer. Vi presenterar en familj av minimalt sammankopplade tidsgrafer med n hörn och (n 2 ) kanter, vilket löser en öppen fråga om (Kempe, Kleinberg, Kumar, JCSS 64, 2002) om förekomsten av glesa tidsanslutning certifikat. Därefter anser vi att problemet med att beräkna en minimivikt delmängd av temporal kanter som bevarar anslutning av en given temporal graf antingen från en given vertex r (r-MTC problem) eller bland alla vertex par (MTC problem). Vi visar att approximabiliteten av r-MTC är nära relaterad till approximabiliteten av Directed Steiner Tree och att r-MTC kan lösas i polynom tid om den underliggande grafen har avgränsat trädbredd. Vi visar också att det bästa approximationsförhållandet för MTC är minst O(2 log 1−ε n ) och högst O(min {n 1+ε, ( och M ) 2/3+ε }), för varje konstant ε > 0, där M är antalet temporala kanter och  till är den maximala graden av den underliggande grafen. Dessutom bevisar vi att den oviktade versionen av MTC är APX-hård och att MTC är effektivt lösbar i träd och 2-ungefärlig i cykler.  ACM Subject Classification Diagram och nätverk är allmänt förekommande inom datavetenskap, eftersom de ger en naturlig och användbar abstraktion av många komplexa system (t.ex. transport- och kommunikationsnät) och processer (t.ex. informationsspridning, epidemier, routing) och även av samspelet mellan enskilda enheter eller partiklar (t.ex. sociala nätverk, kemiska och biologiska nätverk). Traditionella grafteoretiska modeller utgår från att nätverkets struktur och interaktionens styrka är tidsinvarianta. Men, som observerats i t.ex., [3, 19], i många tillämpningar av grafteoretiska modeller, tillgänglighet och vikter av kanterna är faktiskt tid-beroende. Till exempel kan man tänka sig att information sprids och distribueras i dynamiska nätverk (se t.ex. [6, 12, 19, 20] ) av mobila adhoc- och sensornät (se t.ex. [22]) av transportnät och ruttplanering (se t.ex. [3, 15] ), av epidemier, biologiska och ekologiska nätverk (se t.ex. [17, 19] ), och av influensssystem och koevolutionär opinionsbildning (se t.ex. [5, 9] ). Flera varianter av tidsberoende grafer har föreslagits som abstraktioner av sådana inställningar och beräkningsproblem (se t.ex. [6] och hänvisningarna i dessa). Oavsett den specifika varianten är de viktigaste forskningsfrågorna vanligtvis relaterade antingen till att optimera eller utnyttja tidsuppkoppling eller till att beräkna korta tidsrespekteringsvägar (se t.ex., [1, 2, © Kyriakos Axiotis och Dimitris Fotakis; licensierad under Creative Commons License CC-BY Conference titel som denna volym bygger på.
Beviset i REF uppvisar en oändlig familj av tidsuppkopplade grafer med  på (n 2 ) kanter som inte medger o(n 2 )-parse skiftnycklar.
On the Size and the Approximability of Minimum Temporally Connected Subgraphs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}