Gelle Kitti; Iván Szabolcs: Lookahead can help in maximal matching.
Előnézet |
Cikk, tanulmány, mű
cscs_2018_110-113.pdf Letöltés (307kB) | Előnézet |
Absztrakt (kivonat)
In this paper we study a problems in the context of fully dynamic graph algorithms that is, when we have to handle updates (insertions and removals of edges), and answer queries regarding the current graph, preferably in a better time bound than running a classical algorithm from scratch each time a query arrives. We show that a maximal matching can be maintained in an (undirected) graph with a deterministic amortized update cost of O(log m) (where m is the all-time maximum number of the edges), provided that a lookahead of length m is available, i.e. we can “peek” the next m update operations in advance.
| Mű típusa: | Konferencia vagy workshop anyag |
|---|---|
| Befoglaló folyóirat/kiadvány címe: | Conference of PhD Students in Computer Science |
| Dátum: | 2018 |
| Kötet: | 11 |
| Oldalak: | pp. 97-100 |
| Konferencia neve: | Conference of PhD students in computer science (11.) (2018) (Szeged) |
| Befoglaló mű URL: | http://acta.bibl.u-szeged.hu/59477/ |
| Kulcsszavak: | Számítástechnika, Algoritmus, Gráf |
| Megjegyzések: | Bibliogr.: 100. p. ; összefoglalás angol nyelven |
| Feltöltés dátuma: | 2019. nov. 04. 10:10 |
| Utolsó módosítás: | 2022. nov. 08. 10:18 |
| URI: | http://acta.bibl.u-szeged.hu/id/eprint/61776 |
 |
Tétel nézet |
