Lookahead can help in maximal matching
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...
Elmentve itt :
| Szerzők: | |
|---|---|
| Testületi szerző: | |
| Dokumentumtípus: | Könyv része |
| Megjelent: |
2018
|
| Sorozat: | Conference of PhD Students in Computer Science
11 |
| Kulcsszavak: | Számítástechnika, Algoritmus, Gráf |
| Online Access: | http://acta.bibl.u-szeged.hu/61776 |
| LEADER | 01354naa a2200205 i 4500 | ||
|---|---|---|---|
| 001 | acta61776 | ||
| 005 | 20221108101819.0 | ||
| 008 | 191104s2018 hu o 1|| zxx d | ||
| 040 | |a SZTE Egyetemi Kiadványok Repozitórium |b hun | ||
| 041 | |a zxx | ||
| 100 | 1 | |a Gelle Kitti | |
| 245 | 1 | 0 | |a Lookahead can help in maximal matching |h [elektronikus dokumentum] / |c Gelle Kitti |
| 260 | |c 2018 | ||
| 300 | |a 97-100 | ||
| 490 | 0 | |a Conference of PhD Students in Computer Science |v 11 | |
| 520 | 3 | |a 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. | |
| 695 | |a Számítástechnika, Algoritmus, Gráf | ||
| 700 | 0 | 1 | |a Iván Szabolcs |e aut |
| 710 | |a Conference of PhD students in computer science (11.) (2018) (Szeged) | ||
| 856 | 4 | 0 | |u http://acta.bibl.u-szeged.hu/61776/1/cscs_2018_110-113.pdf |z Dokumentum-elérés |