Litun ofurneta - verkefni lokið í Rannsóknasjóði
Verkefnið sneri að því að þróa og greina reiknirit fyrir svokölluð ofurnet, sem eru almenn mynstur með mjög almenna tilvísun og lýsa m.a. skorðum milli eininga svo sem í ýmiss konar bestun.
Verkefnisstjóri var Magnús Már Halldórsson, Háskóla Íslands.
Heiti verkefnis: Litun ofurneta (Hypergraph coloring)
Verkefnisstjóri: Magnús Már Halldórsson, mmh@ru.is
Helsu þátttakendur auk Magnúsar voru Elena Losievskaja og Jaikumar Radhakrishnan
Verkefnið sneri að því að þróa og greina reiknirit fyrir svokölluð ofurnet, sem eru almenn mynstur með mjög almenna tilvísun og lýsa m.a. skorðum milli eininga svo sem í ýmiss konar bestun. Lögð var áhersla á nálgunaraðferðir sem finna stór óháð mengi í ofurnetum með lága gráðu. Ein helsta niðurstaðan úr verkefninu var einfölduð aðferðafræði sem smækkar verkefnið niður í sambærilegt verkefni á venjulegum netum, sem eru auðveldari viðureignar. Með þessari yfirfærsluaðferð mátti svo m.a. leiða út bættar niðurstöður fyrir ýmis reiknirit. Helstu þátttakendur í verkefninu voru Elena Losievskaja, doktorsnemi, og Magnús M. Halldórsson, prófessor, en einnig var haft samstarf við ýmsa aðila erlendis.
Skrá yfir greinar:
- Magnús M. Halldórsson, Elena Losievskaja: Independent Sets in Bounded-Degree Hypergraphs. Proceedings of 10th International Workshop on Algorithms and Data Structures (WADS 2007), Halifax, Kanada, 15-17. ágúst 2007. Lecture Notes in Computer Science 4619. Springer 2007
- Magnús M. Halldórsson, Elena Losievskaja: Independent Sets in Bounded-Degree Hypergraphs. Send til birtingar í tímaritið Discrete Applied Mathematics.
- Magnús M. Halldórsson, Elena Losievskaja: Approximating Independent Sets in Hypergraphs by Semi-definite Programming. Í vinnslu.
Skrá yfir kynningar
5. júlí 2006: ``Greedy Approach to Independent Set Problem in Bounded-Degree Hypergraphs'', EURO 2006 (European Symposium on Operations Research), Reykjavík (EL)
8. nóvember 2006: "Greedy independent sets in hypergraphs". ICE-TCS seminar (EL)
2.mars 2007: ``Independent Sets in Bounded-Degree Hypergraphs'', Stærðfræðimálstofa, Háskóla Íslands (MMH)
6. apríl 2007: ``Independent Sets in Bounded-Degree Hypergraphs'', The 5th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, Sendai, Japan (MMH)
27. apríl 2007: Approximation algorithms for the Maximum Independent set problem in hypergraphs, Algoritmesseminar, Universitetet i Bergen (EL)
15. júní 20007: ``Independent Sets in Bounded-Degree Hypergraphs'', Kyoto International Conference in Computational Geometry and Graph Theory (KyotoCGGT2007), Kyoto, Japan (MMH)
16. ágúst 2007: ``Independent Sets in Bounded-Degree Hypergraphs'', 10th Workshop on Algorithms and Data Structures (WADS), Halifax, Kanada (EL)
Einnig hefur verkefnið verið kynnt á rannsóknadögum, m.a. í Háskóla Íslands.
