Alkalmazott Diszkrét Matematika szeminárium

2012 Tavasz

Vezető: Király Zoltán

Minden második héten, Szerda 10:15-13:00
Pázmány Péter sétány 1/C. 3-607


Hirdetmények


1. alkalom (II. 22.) Kiss Attila

"Folyam-vágás hézag egész- és törtértékű multifolyamokra"
Chekuri, Shepherd és Weibel cikke.

Adott egy elvezetési vagy multifolyam feladat egy H=(V,E(H)) igény gráffal, valamint egy G=(V,E(G)) kiszolgáló gráffal. Ha ez a pár teljesíti a vágás feltételt, akkor ez esetben a folyam-vágás hézag az a legkisebb C érték, melyre létezik megengedett multifolyam H-ban úgy, hogy G minden élére ezt a C értéket írjuk kapacitásnak. Chekuri, Shepherd és Weibel cikkében két speciális gráfosztályt vizsgálnak, amikor G soros-párhuzamos gráf, illetve amikor G síkbarajzolható gráf (speciális esetként az az eset amikor G "k-outerplanar" gráf). Megmutatják, hogy ha G soros-párhuzamos, akkor H-nak létezik egészértékű elvezetése adott folyam-vágás hézaggal G-ben, ha teljesül még néhány feltétel, amelyeket az előadáson meg fogunk tekinteni. Valamint, ha G síkbarajzolható, és H egy speciálisan választott igénygráf, akkor létezik törtértékű elvezetése G-ben, sőt ha G k-outerplanar gráf, akkor H egészértékűen elvezethető G-ben.


2. alkalom (III. 7.) Harkai Alexandra

"Max-színezés és online színezés sávszélességekkel intervallumgráfokon"
Pemmaraju, Raman és Varadarajan cikke.

Operációs rendszerek memória-menedzselése kapcsán kerül elő a max-színezés problémája: egy irányítatlan G=(V,E) gráfon adott egy egészértékű súlyozás, a cél a gráf egy olyan színezésének megtalálása, ahol az egyes színosztályokba tartozó legnagyobb súlyú csúcsok súlyösszege, vagyik a színezés súlya minimális.

Az online színezés általánosítása a max-színezés és a ládapakolás problémáknak: adottak intervallumok (0,1]-beli sávszélességekkel, keressük az intervallumok egy olyan online színezését, ahol az bármely c színre és valós r-re az r-et tartalmazó c színű intervallumok sávszélességeinek összege legfeljebb 1.

A max-színezésre alkalmazott first-fit algoritmus 8-közelítő algoritmust ad, megmutatjuk, hogy a probléma ráadásul NP-nehéz. Az online színezésre Adamy-Erlebach algoritmussal 35-közelítést kapunk, végül az általánosítással kapható algoritmuscsaládban 30-kompetitív algoritmust is mutatunk.


3. alkalom (III. 21.) Király Csaba

"Konstans idejű algoritmusok ritkasági matroidokra"
Ito, Tanigawa és Yoshida cikke.

Egy n pontú gráf gráf (k,l)-kritikus, ha élszáma kn-l, és (k,l)-ritka, azaz az éleinek minden F részhalmaza maximum k|V(F)|-l elemű. Ha egy gráfnak van (k,l)-kritikus részgráfja (ugyanazon ponthalmazon, akkor (k,l)-teljesnek nevezzük. Ismert, hogy a (k,l)-ritka gráfok egy matroid függetlenjeit adják. Ennek a rangfüggvényére adunk konstans idejű közelítő algoritmust korlátos fokú gráfokon. Ennek a segítségével konstans idejű tesztelő-algoritmust kapunk a korlátos fokú gráfok (k,l)-teljességére, azaz konstans időben nagy valószínűséggel el tudjuk dönteni, hogy egy korlátos fokú gráf (k,l)-teljes, vagy nagyon sok élet kell behúznunk ahhoz, hogy az legyen.

Egy digráf gyökeresen (k,l)-élösszefüggő, ha egy r gyökérbél minden csúcsába vezet k éldiszjunkt út és minden csúcsból vezet r-be l éldiszjunkt út. A algoritmusunkat továbbfejlesztve a korlátos fokú gráfok gyökeresen (k,l)-élösszefüggővé irányíthatóságra is adunk egy konstans idejű tesztelő-algoritmust. Végül megmutatjuk, hogy egyik problémára sem adható konstans idejű egy-oldalú tesztelő-algoritmus, azaz olyan tesztelő, ami a tulajdonság teljesülése esetén 1 valószínűséggel elfogadó állapotban áll le.


4. alkalom (IV. 11.) Csizmadia Balázs

"Hálózati hibák érzékelése és a gráf-összefüggőség kapcsolata"
Kleinberg, Sandler és Slivkins cikke.

Az előadás során egy hálózaton belüli él illetve csúcshibák esetén szeretnénk detektálni, hogy összefüggő maradt-e a hálózat (gráf). Végig (epszilon, k) hibákkal fogunk foglalkozni, amelyről akkor beszélünk, ha k darab csúcs illetve él elhagyása után a gráfnak van legalább kettő darab n-szer epszilon méretű komponense, ahol n a csúcsok számát jelöli. Egy D csúcshalmazról azt mondjuk, hogy (epszilon, k) detektor, ha minden (epszilon, k) hiba esetén D valamelyik két csúcsa nem tud kommunikálni (különböző komponensbe kerülnek). Ismeretes, hogy bármely gráfra van k és epszilon polinomja méretű detektor, függetlenül a gráf méretétől. Az előadás során a detektorok méretei és az él- illetve csúcsösszefüggőség közti kapcsolatokat vizsgáljuk.


5. alkalom (IV. 25.) Király Zoltán

"Fokszámsorozatok realizációi"

Adott természetes számok egy sorozata, erről elég könnyen eldönthető, hogy egy egyszerű gráf fokszámsorozata-e. A mi célunk, hogy az összes realizációt legeneráljuk. Persze nagyon sok realizáció lehet, ezért a célunk az, hogy mindig O(n^2) lépés után kiírjuk egy újabb realizáció szomszédsági mátrixát. Persze arra is ügyelünk, hogy minden realizációt pontosan egyszer írjunk ki.


6. alkalom (V. 9.) Hubai Tamás

"Minimum Maximum-Degree Publish-Subscribe Overlay Network Design"
Onus és Richa cikke.

Valós idejű kommunikációs rendszereknél sokszor használják a publish/subscribe elvet: a résztvevők feliratkoznak néhány témára, ami őket érdekli, és egymás között továbbítják a megfelelő üzeneteket. Ahhoz, hogy egy ilyen peer-to-peer rendszer hatékony legyen, azt szeretnénk, hogy az üzeneteket csak olyan résztvevőknek kelljen továbbítaniuk, akiket érdekel is, és minél kevesebb másik résztvevőnek.

Formálisan ez azt jelenti, hogy adott a csomópontok és a témák halmaza, továbbá minden csomópontról tudjuk, hogy mely témákra iratkozott fel. Kössük össze a csomópontokat egy minél kisebb maxfokú gráffá, ahol az egy témára feliratkozott csomópontok összefüggő részgráfot alkotnak.

A cikk első része egy polinomiális közelítő algoritmust ad a feladatra, ahol a tényleges és az optimális maxfok aránya logaritmikus a feliratkozások számában. A témák számának a logaritmusánál jobb közelítési arányt nem is lehet elérni (hacsak nem P=NP).

A második, kevésbé formális részben kísérleti úton összehasonlítjuk az algoritmus hatékonyságát a jelenlegi legelterjedtebb módszerrel, illetve heurisztikus algoritmusokat adunk arra az esetre, ha a gráf átmérőjét is szeretnénk 2-re korlátozni.