Mihálykó András: Approximációs algoritmusok globális merevségi kérdésekre

Két dimenzióban egy minimális költségű merev gráfot könnyedén ki tudunk választani. De ha a kérdés már globális merevség, a kérdés rögtön nehéz lesz. Előadásomban röviden ismertetem García és Tejel cikkét, melyben egy Laman gráfot növelnek minimális számú éllel redundánsan merevvé, majd bemutatom, hogyan lehet ebből egy 2-közelítő algoritmust kihozni arra a kérdésre, hogy egy metrikus teljes gráf esetén mi a minimális költségű globálisan merev részgráf. Elmondom mit tudunk a 3 dimenziós esetre, illetve arra, ha minimális élszámú globálisan merev részgráfot keresünk egy nem teljes gráfban.
A téma egyáltalán nem kerek, lezárt, ezért sok közérthető nyitott kérdéssel is szolgálok majd.