Varnyú József: Synchronized Traveling Salesman Problem

Az előadáson Pap Gyulával közös készülő cikkünket ismertetem, amiben definiáljuk az ún. szinkronizált utazó ügynök problémát. Egy irányítatlan gráfon egyszerre lépkednek ügynökök úgy, hogy nem találkozhatnak sem a csúcsokon, sem pedig az éleken egymással szemben haladva. A kérdés, hogy egy gráfra mi a legkisebb α szám, hogy legalább n/α ügynök legfeljebb nα lépésben bejárja az összes csúcsot és visszatér a saját kezdőcsúcsába. Általános esetben a probléma NP-nehéz, mivel α=1 akkor és csak akkor, ha a gráf tartalmaz Hamilton-kört. A cikkben két speciális esettel foglalkozunk: ha a gráf fa, illetve ha 3-reguláris és 2-összefüggő.