<p>The densest subgraph problem is an important problem with both theoretical and practical significance. We consider a variant of the problem, the directed densest subgraph problem, under the partially dynamic setting of edge insertions only. We give a algorithm maintaining a (1-ε)-approximate directed densest subgraph in O(log³n/ε⁶) amortized time per edge insertion, based on earlier work by Chekuri and Quanrud. This result partially improves on an earlier result by Sawlani and Wang, which guarantees O(log⁵n/ε⁷) worst case time for edge insertions and deletions.</p>

京都大学 / 新制・課程博士 / 博士(情報学) / 甲第24730号 / 情博第818号 / 新制||情||138(附属図書館) / 京都大学大学院情報学研究科知能情報学専攻 / (主査)教授 阿久津 達也, 教授 山本 章博, 教授 岡部 寿男 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

No description available.

Darbe trumpai apžvelgtos figūrų pakavimo ištakos, aprašyti keli figūrų pakavimui naudojami stochastinio modeliavimo algoritmai. Išnagrinėtas perturbacijos metodas, sukurtos dvi šiuo metodu vienetiniame kvadrate vienodus apskritimus pakuojan��ios programos, detaliai aprašyti jų algoritmai. Eksperimentiškai ištirtos programų galimybės: kiekviena programa po 30 kartų buvo pakuojami n apskritimų, kur 3 ≤ n ≤ 15 ir n = 25, 50, 75, 100. Buvo fiksuojami ir apibendrinami pakavimų rezultatai. Pastarieji lyginti tarpusavy ir kartu su Violetos Sabonienės magistriniame darbe ,,Biliardinio modeliavimo algoritmai ieškant talpiausio geometrinių figūrų pakavimo“ biliardiniu metodu atliktais pakavimo rezultatais. Prieduose pateikti programų tekstai ir skaičiavimų lentelės. / In this work are examined the sources of figure packing, described the stochastic simulation algorithms of finding the densest packing of geometric figures. Here is analysed the method of perturbation and made two programmes of equal circle packing in unit square and their algorithms are being described in detail. The possibilities of programmes were analysed experimentally: using each programme 30 times. In each experiment were packed n circles, were 3 ≤ n ≤ 15 end n = 25, 50, 75, 100. The results of packing were fixed and summarized. The latter rezults were compared between themselves and also with the results of Violeta Sabonienė master of science work “The billiarding simulation algorithms of finding the densest packing of geometric figures“. The text and the calculation charts of the program are giver in the appendices.