|
Title:
|
DYNAMIC CONNECTIVITY:
THE STAR AND THE TREE STORY |
|
Author(s):
|
George Lagogiannis |
|
ISBN:
|
978-989-8704-24-5 |
|
Editors:
|
Hans Weghorn |
|
Year:
|
2020 |
|
Edition:
|
Single |
|
Keywords:
|
Dynamic Connectivity, Logarithmic, Worst Case, Dynamic Trees |
|
Type:
|
Full |
|
First Page:
|
3 |
|
Last Page:
|
10 |
|
Language:
|
English |
|
Cover:
|
|
|
Full Contents:
|
click to dowload 
|
|
Paper Abstract:
|
In this paper we deal with the dynamic connectivity problem, targeting deterministic worst-case logarithmic time
complexities. We present an algorithm that achieves all the operations in logarithmic worst -case time, on a graph that
consists of a star and a forest (of trees), both defined on the same set of vertices. This graph is more complicated than a
forest on which deterministic worst-case logarithmic time complexities have already been obtained by means of the
Dynamic Trees algorithm, introduced by Sleator and Tarjan (1983). For implementing the operations we build upon
Dynamic Trees. |
|
|
|
|
|
|
