Leírás
Alkalmazott Diszkrét Matematika szeminárium
Absztrakt:
A kombinatorikus optimalizálás egyik legnépszerűbb problémája az utazó ügynök
probléma. Ennek egy speciális esete a grafikus utazó ügynök probléma, amikor a
gráf összes élét egység hosszúnak választjuk. Zdenek Dvorak, Daniel Kral,
Bojan Mohar cikkében a probléma ezen változatát vizsgálták 3 reguláris
("cubic") gráfokon.
Először a problémát egy 3 regularis gráf 2-összefüggő részgráfjain vizsgálták
("subcubic", 2-összefüggő gráfokon). Jelöljük a gráf csúcsainak számát
n-nel, a másodfokú csúcsainak számát pedig n_2-vel. (Egy ilyen "subcubic"
gráfban minden csúcs foka legfeljebb 3.)
Megmutatták, hogy ezen a nagyobb gráfosztályon létezik polinomális algoritmus,
ami előállít egy legfeljebb (9/7)n + (2/7)n_2 -1 hosszú TSP
sétát, azaz olyan zárt sétát, ami minden csúcsot legalább egyszer
érint. Ezzel kapjuk a cikk fő állítását, azaz
hogy létezik polinomális idejű (9/7)-approximáló algoritmus a grafikus
utazó ügynök problémára 2-összefüggő 3-reguláris gráfokon.
For Teams access please contact Zoltán Király (kiraly[at]cs.elte.hu).