Gelle Kitti and Iván Szabolcs: DFS is unsparsable and lookahead can help in maximal matching. In: Acta cybernetica, (23) 3. pp. 887-902. (2018)
Preview |
Cikk, tanulmány, mű
actacyb_23_3_2018_10.pdf Download (512kB) | Preview |
Abstract
In this paper we study two 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 with a better time bound than that when running a classical algorithm from scratch each time a query arrives. In the first part we show that there are dense (directed) graphs having no nontrivial strong certificates for maintaining a depth-first search tree, hence the so-called sparsification technique cannot be applied effectively to this problem. In the second part, 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 “take a peek” at the next m update operations in advance.
| Item Type: | Article |
|---|---|
| Journal or Publication Title: | Acta cybernetica |
| Date: | 2018 |
| Volume: | 23 |
| Number: | 3 |
| ISSN: | 0324-721X |
| Page Range: | pp. 887-902 |
| Language: | English |
| Place of Publication: | Szeged |
| Related URLs: | http://acta.bibl.u-szeged.hu/55467/ |
| Uncontrolled Keywords: | Gráf, Algoritmus |
| Additional Information: | Bibliogr.: p. 901-902. ; összefoglalás angol nyelven |
| Subjects: | 01. Natural sciences 01. Natural sciences > 01.02. Computer and information sciences |
| Date Deposited: | 2018. Nov. 08. 08:50 |
| Last Modified: | 2022. Jun. 21. 08:17 |
| URI: | http://acta.bibl.u-szeged.hu/id/eprint/55683 |
Actions (login required)
 |
View Item |
